Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00515
Orderpreserving Drawings of Trees with Approximately Optimal Height (and Small Width)
Johannes Batzill and
Therese Biedl
Vol. 24, no. 1, pp. 119, 2020. Regular paper.
Abstract In this paper, we study how to draw trees so that they are planar, straightline 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 socalled pathwidth) is a known lower bound on the height of the tree $T$.
Hence our algorithm provides an asymptotic 2approximation 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 orderpreserving straightline 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

Journal Supporters
