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.
展开▼
机译：在本文中，我们研究如何绘制树木，使它们是平面，直线并尊重每个节点周围的边缘的给定顺序。我们专注于最小化高度，并表明我们可以始终实现最多2PW（T）+ 1 $的高度，其中$ PW（t）$（所谓的路径）是高度的已知下限树$ t $。因此，我们的算法为最佳高度提供了渐近2近似。这种绘图的宽度可以不是节点数量的多项式。因此，我们给出了一种创建图纸的第二种方式，其中高度最多为3pW（t）$，并且宽度可以通过节点的数量限制。最后，我们构建了树木$ T $，需要在所有平面令保存的直线图形中获得高度2PW（T）+ 1美元。
展开▼
