Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00424
Drawing Planar Graphs with Reduced Height
Vol. 21, no. 4, pp. 433-453, 2017. Regular paper.
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.
|
Submitted: August 2016.
Reviewed: December 2016.
Revised: January 2017.
Accepted: January 2017.
Final: January 2017.
Published: February 2017.
Communicated by
Giuseppe Liotta
|
Journal Supporters
|