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.


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.

Download: [img] Postscript - Preprinted Version
Download (338kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2002-431
Depositing User: Christoph Buchheim
Date Deposited: 02 Feb 2003 00:00
Last Modified: 12 Jan 2012 11:56