Minimum-Area Drawings of Plane 3-Trees

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.