Drawing Planar Graphs with Reduced Height

Abstract

A polyline (resp., straight-line) drawing $\Gamma$ of a planar graph $G$ on a set $L_k$ of $k$ parallel lines is a planar drawing that maps each vertex of $G$ to a distinct point on $L_k$ and each edge of $G$ to a polygonal chain (resp., straight line segment) between its corresponding endpoints, where the bends lie on $L_k$. The height of $\Gamma$ is $k$, i.e., the number of lines used in the drawing. In this paper we establish 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 $\Delta$, having an edge separator of size $\lambda$, admits a polyline drawing with height $4n/9+O(\lambda)$, where the previously best known bound was $2n/3$. Since $\lambda\in O(\sqrt{n\Delta})$, this implies the existence of a drawing of height at most $4n/9+o(n)$ for any planar triangulation with $\Delta \in 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 graph.