Drawing Planar Graphs with Reduced Height

Abstract. A straight-line (respectively, polyline) drawing Γ of a planar graph G on a set Lk of k parallel lines is a planar drawing that maps each vertex of G to a distinct point on Lk and each edge of G to a straight line segment (respectively, a polygonal chain with the bends on Lk) between its endpoints. The height of Γ is k, i.e., the number of lines used in the drawing. In this paper we compute new upper bounds on the height of polyline drawings of planar graphs using planar separators. Specifically, we show that every n-vertex planar graph with maximum degree ∆, having a simple cycle separator of size λ, admits a polyline drawing with height 4n/9+O(λ∆), where the previously best known bound was 2n/3. Since λ ∈ O(√n), this implies the existence of a drawing of height at most 4n/9 + o(n) for any planar triangulation with ∆ ∈ o(√n). For n-vertex planar 3-trees, we compute straight-line drawings with height 4n/9 +O(1), which improves the previously best known upper bound of n/2. All these results can be viewed as an initial step towards compact drawings of planar triangulations via choosing a suitable embedding of the input graph.