NP-Completeness of Minimal Width Unordered Tree Layout

Authors

  • Kim Marriott
  • Peter Stuckey

DOI:

https://doi.org/10.7155/jgaa.00093

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.

Downloads

Download data is not yet available.

Downloads

Published

2004-01-01

How to Cite

Marriott, K., & Stuckey, P. (2004). NP-Completeness of Minimal Width Unordered Tree Layout. Journal of Graph Algorithms and Applications, 8(3), 295–312. https://doi.org/10.7155/jgaa.00093

Issue

Section

Articles

Categories