Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00222 Minimum-Area Drawings of Plane 3-Trees Debajyoti Mondal , Rahnuma Islam Nishat , Md. Saidur Rahman , and Muhammad Jawaherul Alam Vol. 15, no. 2, pp. 177-204, 2011. Regular paper Abstract A straight-line grid drawing of a plane graph G is a planar drawing of G, where each vertex is drawn at a grid point of an integer grid and each edge is drawn as a straight-line segment. The height, width and area of such a drawing are respectively the height, width and area of the smallest axis-aligned rectangle on the grid which encloses the drawing. A minimum-area drawing of a plane graph G is a straight-line grid drawing of G where the area is the minimum. It is NP-complete to determine whether a plane graph G has a straight-line grid drawing with a given area or not. In this paper we give a polynomial-time algorithm for finding a minimum-area drawing of a plane 3-tree. Furthermore, we show a ⎣[(2n)/3]−1⎦×2⎡[(n)/3]⎤ lower bound for the area of a straight-line grid drawing of a plane 3-tree with n ≥ 6 vertices, which improves the previously known lower bound ⎣[(2(n−1))/3]⎦×⎣[(2(n−1))/3]⎦ for plane graphs. We also explore several interesting properties of plane 3-trees. Keywords. Graph drawing, Minimum area, Minimum layer, Plane 3-tree, Lower bound.
|
Published: February 2011. Revised: November 2010. Submitted: July 2010. Reviewed: October 2010. Final: December 2010. Accepted: November 2010. Communicated by Giuseppe Liotta |
Journal of Graph Algorithms and Applications |