NP-Completeness of Minimal Width Unordered Tree Layout - Marriott, Kim; Stuckey, Peter (Journal of Graph Algorithms and Applications, 2004)
Tree layouthas received considerable attention because of its practicalimportance. Arguably the most common drawing conventionis the (ordered) layered tree convention for rooted trees in which thelayout is required to preserve the relative order of a node's children. However,in some applications preserving the ordering of children is not important, andconsiderably more compact layout can be achieved if this requirementis dropped. Here we introduce the unorderedlayered tree drawing convention for binary rooted trees and show thatdetermining a minimal width drawing for this convention is NP-complete. <!---->