Order-preserving Drawings of Trees with Approximately Optimal Height (and Small Width)

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.