NP-completeness of minimal width unordered tree layout

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


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
Number of pages18
ISBN (Electronic)9789812773289
ISBN (Print)981256845X, 9789812568458
Publication statusPublished - 1 Jan 2006

Cite this