Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00093 NP-Completeness of Minimal Width Unordered Tree Layout Kim Marriott and Peter J. Stuckey Vol. 8, no. 3, pp. 295-312, 2004. Regular paper Abstract 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.
|
Submitted: May 2003. Revised: June 2005. Communicated by Michael Kaufmann |
Journal of Graph Algorithms and Applications |