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: [img] Postscript - Preprinted Version
Download (162kB) | Preview
Download: [img] PDF - Preprinted Version
Download (111kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: [error in script] 1 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
  • 68-XX Computer science > 68Qxx Theory of computing

  • Uncontrolled Keywords: Graph Drawing, Binary Trees, NP-completeness
    Subjects: 68-XX Computer science > 68Qxx Theory of computing
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Depositing User: Christoph Buchheim
    Date Deposited: 17 Feb 2004 00:00
    Last Modified: 12 Jan 2012 10:42
    Deposit Information:
    ZAIK Number: [error in script]
    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