Optimum-width upward order-preserving poly-line drawings of trees.
Thérèse Biedl · arXiv (Cornell University) · 2015
An upward drawing of a tree is a drawing such that no parents are below their children. It is order-preserving if the edges to children appear in prescribed order around each vertex. Chan showed that any tree has an upward order-preserving drawing with width $O(\log n)$. In this paper, we consider upward order-preserving drawings where edges are allowed to have bends. We present a linear-time algorithm that finds such drawings with instance-optimal width, i.e., the width is the minimum-possible for the input tree. We also briefly study order-preserving upward straight-line drawings, and show that some trees require larger width if drawings must additionally be straight-line.