Improving Walker's Algorithm to Run in Linear Time

Buchheim, Christoph and Jünger, Michael and Leipert, Sebastian (2002) Improving Walker's Algorithm to Run in Linear Time.
Published in: Graph drawing : 10th international symposium, GD 2002, Irvine, CA, USA, August 26 - 28, 2002 ; revised papers, Lecture notes in computer science. 2528 Springer 2002, pp. 347-364.

Abstract

The algorithm of Walker is widely used for drawing trees of unbounded degree, and it is widely assumed to run in linear time, as the author claims in his article. But the presented algorithm obviously needs quadratic runtime. We explain the reasons for that and present a revised algorithm that creates the same layouts in linear time.


Actions:
Download: [img] Postscript - Preprinted Version
Download (330Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Proceedings article
Citations: No citation data.
Uncontrolled Keywords: graph drawing trees 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
    Related URLs:
    Deposit Information:
    ZAIK Number: zaik2002-431
    Depositing User: Christoph Buchheim
    Date Deposited: 02 Feb 2003 00:00
    Last Modified: 12 Jan 2012 11:56
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/431