On the complexity of drawing trees nicely: corrigendum

Akkerman, Thorsten and Buchheim, Christoph and Jünger, Michael and Teske, Daniel (2004) On the complexity of drawing trees nicely: corrigendum. [Journal (Paginated)]

Full text not available from this repository.

Abstract

In this journal, Supowit and Reingold have given a proof that it is NP-complete to decide whether a binary tree can be drawn on a grid with width 24 if certain aesthetic requirements are obeyed. We identify and repair a mistake in their proof.

Item Type:Journal (Paginated)
Additional Information:10.1007/s00236-004-0138-y
Keywords:Trees, width minimization
Classifications:G Algorithms and Complexity > G.070 Area / Edge Length
ID Code:623

Repository Staff Only: item control page

References

Supowit, J., Reingold, B.M.: The complexity of drawing trees nicely. Acta Informatica 18, 377-392 (1983)