|
In a convex grid drawing of a plane graph, every edge is drawn as a straight-line segment without any edge-intersection, every vertex is located at a grid point, and every facial cycle is drawn as a convex polygon. A plane graph <l>G</l> has a convex drawing if and only if <l>G</l> is internally triconnected. It has been known that an internally triconnected plane graph <l>G</l> of <l>n</l> vertices has a convex grid drawing on a grid of <l>O(n3)</l> area if the triconnected component decomposition tree of <l>G</l> has at most four leaves. In this paper, we improve the area bound <l>O(n3)</l> to <l>O(n2)</l>, which is optimal within a coefficient. More precisely, we show that <l>G</l> has a convex grid drawing on a <l>2n x 4n</l> grid. We also present an algorithm to find such a drawing in linear time.
|
