Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00222
MinimumArea Drawings of Plane 3Trees
Vol. 15, no. 2, pp. 177204, 2011. Regular paper.
Abstract A straightline 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 straightline segment. The height, width and area of such a drawing are respectively the height, width and area of the smallest axisaligned rectangle on the grid which encloses the drawing. A minimumarea drawing of a plane graph G is a straightline grid drawing of G where the area is the minimum. It is NPcomplete to determine whether a plane graph G has a straightline grid drawing with a given area or not. In this paper we give a polynomialtime algorithm for finding a minimumarea drawing of a plane 3tree. Furthermore, we show a ⎣[(2n)/3]−1⎦×2⎡[(n)/3]⎤ lower bound for the area of a straightline grid drawing of a plane 3tree 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 3trees.
Keywords. Graph drawing, Minimum area, Minimum layer, Plane 3tree, Lower bound. 
Submitted: July 2010.
Reviewed: October 2010.
Revised: November 2010.
Accepted: November 2010.
Final: December 2010.
Published: February 2011.
Communicated by
Giuseppe Liotta
