Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00093
NP-Completeness of Minimal Width Unordered Tree Layout
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.
|
Journal Supporters
|