Drawing Rooted Trees in Linear Time

Buchheim, Christoph and J√ľnger, Michael and Leipert, Sebastian (2006) Drawing Rooted Trees in Linear Time.
Published in: Software; Practice and Experience Vol. 36 (6). pp. 651-665.

Abstract

The aim of automatic graph drawing is the development of algorithms for creating nice and well-readable layouts of abstractly given graphs. For the special case of rooted trees of unbounded degree, John Q. Walker II presented a drawing algorithm in this journal in 1990. This algorithm is an extension of the Reingold-Tilford algorithm. It yields very good results and is therefore widely used in practice. Furthermore, it is widely assumed to run in linear time, as the author claims in his article. However, the algorithm in its presented form clearly needs quadratic runtime. We explain the reasons for that and state a revised algorithm that creates the same layouts in linear time.


Actions:
Full text not available from this repository.
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: [error in script] 6 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C85 Graph algorithms

  • 05-XX Combinatorics > 05Cxx Graph theory > 05C05 Trees

  • Uncontrolled Keywords: graph drawing, trees, Reingold-Tilford algorithm, Walker's algorithm
    Subjects: 05-XX Combinatorics > 05Cxx Graph theory > 05C85 Graph algorithms
    05-XX Combinatorics > 05Cxx Graph theory > 05C05 Trees
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Depositing User: Christoph Buchheim
    Date Deposited: 03 Jun 2005 00:00
    Last Modified: 08 Jul 2013 08:12
    Deposit Information:
    ZAIK Number: [error in script]
    Depositing User: Christoph Buchheim
    Date Deposited: 03 Jun 2005 00:00
    Last Modified: 08 Jul 2013 08:12
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/483