NP-completeness of minimal width unordered tree layout

Research output: Chapter in Book/Report/Conference proceedingChapter (Book)Researchpeer-review

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.

Original languageEnglish
Title of host publicationGraph Algorithms and Applications 5
PublisherWorld Scientific Publishing
Pages295-312
Number of pages18
ISBN (Electronic)9789812773289
ISBN (Print)981256845X, 9789812568458
DOIs
Publication statusPublished - 1 Jan 2006

Cite this

Marriott, K., & Stuckey, P. J. (2006). NP-completeness of minimal width unordered tree layout. In Graph Algorithms and Applications 5 (pp. 295-312). World Scientific Publishing. https://doi.org/10.1142/9789812773289_0016