NP-completeness of minimal width unordered tree layout. (English) Zbl 1088.68070

Summary: Tree layout has received considerable attention because of its practical importance. Arguably the most common drawing convention is the (ordered) layered tree convention for rooted trees in which the layout is required to preserve the relative order of a node’s children. However, in some applications preserving the ordering of children is not important, and considerably more compact layout can be achieved if this requirement is dropped. Here we introduce the unordered layered tree drawing convention for binary rooted trees and show that determining a minimal width drawing for this convention is NP-complete.


68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI EuDML