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.
 Convex Grid Drawings of Plane Graphs with Pentagonal ContoursKazuyuki MIURA  Publication IEICE TRANSACTIONS on Information and Systems   Vol.E97-D   No.3   pp.413-420Publication Date: 2014/03/01 Online ISSN: 1745-1361 DOI: 10.1587/transinf.E97.D.413 Print ISSN: 0916-8532Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science —New Trends in Theory of Computation and Algorithm—)Category: Graph AlgorithmsKeyword: algorithm,  convex grid drawing,  graph drawing,  plane graph,  triconnected,  Full Text: PDF>> Buy this Article Summary:  In a convex drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection and all facial cycles are drawn as convex polygons. In a convex grid drawing, all vertices are put on grid points. A plane graph G has a convex drawing if and only if G is internally triconnected, and an internally triconnected plane graph G has a convex grid drawing on an (n-1)×(n-1) grid if either G is triconnected or the triconnected component decomposition tree T(G) of G has two or three leaves, where n is the number of vertices in G. An internally triconnected plane graph G has a convex grid drawing on a 2n×2n grid if T(G) has exactly four leaves. In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 6n×n2 grid if T(G) has exactly five leaves. We also present an algorithm to find such a drawing in linear time. This is the first algorithm that finds a convex grid drawing of such a plane graph G in a grid of polynomial size.