Convex Grid Drawings of Plane Graphs with Rectangular Contours - Miura, Kazuyuki; Kamada, Akira; Nishizeki, Takao (Journal of Graph Algorithms and Applications, 2008)
In a convex drawing of a plane graph,all edges are drawn as straight-line segments without any edge-intersection andall 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 drawingif 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) gridif either G is triconnected orthe triconnected component decomposition tree T(G) of G has two or three leaves,where n is the number of vertices in G.In this paper, we show thatan internally triconnected plane graph G has a convex grid drawingon a 2n ×n2 grid if T(G) has exactly four leaves.We also present an algorithm to find such a drawing in linear time.Our convex grid drawing has a rectangular contour,while most of the known algorithmsproduce grid drawings having triangular contours. <!---->