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. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 344-353 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_32).
This is the latest version of this item.
Full text not available from this repository.
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 clearly needs quadratic runtime. We explain the reasons for that and present a revised algorithm that creates the same layouts in linear time.
Available Versions of this Item
Repository Staff Only: item control page