For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Straight-Line Grid Drawings of Generalized Doughnut Graphs
Tomohiro SOETA Kazuyuki MIURA
D - Abstracts of IEICE TRANSACTIONS on Information and Systems (Japanese Edition)
Publication Date: 2018/03/01
Online ISSN: 1881-0225
Type of Manuscript: Special Section PAPER (Special Section on Student Research)
graph drawing, straight-line grid drawing, plane graph, doughnut graph,
Full Text(in Japanese): PDF(647.3KB)
>>Buy this Article
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 . 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).