Improving Walker’s algorithm to run in linear time
Graph Drawing
Affiliations
1Universität zu Köln, Institut für Informatik, Pohligstraße 1, 50969 Köln, Germany
2caesar research center, Friedensplatz 16, 53111 Bonn, Germany
Abstract
The algorithm of Walker [5] 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.