Improving Walker's Algorithm to Run in Linear Time
Buchheim, Christoph and Jünger, Michael and Leipert, Sebastian
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.
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.
|Item Type:||Proceedings article|
|Citations:||No citation data.|
|Uncontrolled Keywords:||graph drawing trees Walker's algorithm|
|Divisions:||Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger|
|Depositing User:||Christoph Buchheim|
|Date Deposited:||02 Feb 2003 00:00|
|Last Modified:||12 Jan 2012 11:56|