Order-preserving Drawings of Trees with Approximately Optimal Height (and Small Width)
Johannes Batzill and Therese Biedl
Vol. 24, no. 1, pp. 1-19, 2020. Regular paper.
Abstract In this paper, we study how to draw trees so that they are planar, straight-line and respect a given order of edges around each node. We focus on minimizing the height, and show that we can always achieve a height of at most $2pw(T)+1$, where $pw(T)$ (the so-called pathwidth) is a known lower bound on the height of the tree $T$. Hence our algorithm provides an asymptotic 2-approximation to the optimal height. The width of such a drawing may not be a polynomial in the number of nodes. Therefore we give a second way of creating drawings where the height is at most $3pw(T)$, and where the width can be bounded by the number of nodes. Finally we construct trees $T$ that require height $2pw(T)+1$ in all planar order-preserving straight-line drawings.
Submitted: December 2018.
Reviewed: May 2019.
Revised: July 2019.
Accepted: October 2019.
Final: October 2019.
Published: January 2020.
Communicated by Csaba D. Tóth
article (PDF)