A study of convex grid drawing algorithms of plane graphs with contours of k-gon

点击翻译按钮获取中文摘要

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.In this study, we first show that an internally triconnected plane graph G has a convex grid drawing on a 2n x 2n grid if the triconnected component decomposition tree T(G) has exactly four leaves. We also present an algorithm to find such a drawing in linear time. We then show that an internally triconnected plane graph G has a convex grid drawing on a 6n x n2 grid if T(G) has exactly five leaves. We also present an algorithm to find such a drawing in linear time. Furthermore, We show that an internally triconnected plane graph G has a convex grid drawing on a 6n x n2 grid if T(G) has exactly six leaves. We also present an algorithm to find such a drawing in linear time.