We investigate the complexity of producing aesthetically pleasing
drawings of binary trees, drawings that are as narrow as possible. The notion
of what is aesthetically pleasing is embodied in several constraints on the
placement of nodes, relative to other nodes. Among the results we give are:
(1) There is no obvious "principle of optimality" that can be applied, since
globally narrow, aesthetic placements of trees may require wider than
necessary subtrees. (2) A previously suggested heuristic can produce drawings
on n-node trees that are O(n) times as wide as necessary. (3) The problem
can be reduced in polynomial time to linear programming; hence, if the
coordinates assigned to the nodes are continuous variables, then the problem
can be solved in polynomial time. (4) If the placement is restricted to the
integral lattice then the problem is NP-hard, as is its approximation to
within a factor of about 4 per cent.
On the complexity of drawing trees nicely: corrigendum (PDF; 5 pages)
By Thorsten Akkerman, Christoph Buchheim, Michael Jünger,
and Daniel Teske
Acta Informatica 40 (2004), 603-607