Tree visualizations are useful for displaying hierarchical structures such as family trees and subdirectories. An ideal drawing of such a tree is planar (no crossing), upward (parents are above children), straight-line (no bends) and order-preserving (the children appear in prescribed order).

In this talk, I will present two linear-time algorithms that find planar upward tree-drawings with instance-optimal width, i.e., the width is the minimum-possible for the input tree. These algorithms are for two different relaxations of “ideal drawings”. In the first model, the drawings need not be order-preserving; a very simple algorithm then finds straight-line drawings of optimal width. In the second model, the drawings must be order-preserving; and the algorithm finds optimum-width poly-line drawings, i.e., edges are allowed to have bends.