Straight-Line Grid Drawings of Generalized Doughnut Graphs

Tomohiro SOETA  Kazuyuki MIURA  

Publication
D - Abstracts of IEICE TRANSACTIONS on Information and Systems (Japanese Edition)   Vol.J101-D   No.3   pp.494-501
Publication Date: 2018/03/01
Online ISSN: 1881-0225
DOI: 
Type of Manuscript: Special Section PAPER (Special Section on Student Research)
Category: 
Keyword: 
graph drawing,  straight-line grid drawing,  plane graph,  doughnut graph,  

Full Text(in Japanese): PDF(647.3KB)
>>Buy this Article


Summary: 
A straight-line grid drawing of a plane graph G is a drawing of G on the plane so that all vertices of G are put on plane grid points and all edges are drawn as straight line segments between their endpoints without edge-intersection. It is known that every plane graph G has a straight-line grid drawing on an (n-2)×(n-2) grid if G has n vertices [15]. On the other hands, a restricted class of graphs may have a more compact straight-line grid drawing. In this paper, we define a “five-connected p-k doughnut graph” and give a linear-time algorithm to find a straight-line grid drawing of the five-connected p-k doughnut graph on a n/(2k-2)+(2k-5) × (2k-1) grid, that is O(n). Furthermore, we define a “four-connected (resp. triconnected)p-k doughnut graph” and give a linear-time algorithm to find a straight-line grid drawing of the four-connected (resp. triconnected)p-k doughnut graph on a n/(2k-2)+(2k-5) × (2k-1) grid, that is O(n).