Faster Algorithms for Grid and Layered Drawings of Plane 3-Trees
摘要
A grid drawing of a plane graph G is a planar drawing of G such that each vertex is mapped to an integer grid point and each edge is mapped to a straight line segment with the endpoints determined by its end vertices. The area of a grid drawing is the area of the smallest axis-aligned rectangle that encloses the drawing. A k-layer drawing of G is a planar drawing on a set L of k horizontal lines such that each vertex is mapped to a point on L and each edge is mapped to a straight line segment. A minimum area (minimum-layer) drawing of G is a straight-line grid (layered) drawing of G where the area (number of layers) is minimized. In this paper we examine the grid and layered drawing of a well-studied class of planar graphs called plane 3-tree. Given a n-vertex plane 3-tree, one can compute a straight line drawing with minimum number of layers or area in \(O(n^5)\) and \(O(n^9\log n)\) time, respectively [Mondal et al., JGAA, 15(2), 2011]. Here we improve the running times to \(O(n^3)\) and \(O(n^7\log n)\) , respectively. We then give a fast approximation algorithm for computing minimum-layer drawings for a nontrivial subclass of plane 3-trees.