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.
Published in:
Acta Informatica Vol. 40 (8).
pp. 603-607.
Abstract
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.
Actions:
Download: |
Download (162kB) | Preview |
---|---|
Download: |
Download (111kB) | Preview |
Editorial actions: | ![]() |
Content information:
Item Type: | Article |
---|---|
Citations: | 1 (Google Scholar) | |
Uncontrolled Keywords: | Graph Drawing Binary Trees NP-completeness |
Subjects: |
|
Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger |
Related URLs: |
Deposit Information:
ZAIK Number: | zaik2004-465 |
---|---|
Depositing User: | Christoph Buchheim |
Date Deposited: | 17 Feb 2004 00:00 |
Last Modified: | 12 Jan 2012 10:42 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/465 |