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.

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.

Item Type:Conference Paper
Additional Information:10.1007/3-540-36151-0_32
Classifications:G Algorithms and Complexity > G.999 Others
M Methods > M.900 Tree
ID Code:227

Available Versions of this Item

Repository Staff Only: item control page

References

C. Buchheim, M. Jünger, and S.Leipert. Improving Walker's algorithm to run in linear time. Technical Report zaik2002-431, ZAIK, Universität zu Köln, 2002.

E. Reingold and J. Tilford. Tidier drawings of trees. IEEE Transactions on Software Engineering, 7(2):223-228, 1981.

B. Schieber and U. Vishkin. On finding lowest common ancestors: Simplification and parallelization. In Proceedings of the Third Aegean Workshop on Computing, volume 319 of Lecture Notes in Computer Science, pages 111-123, 1988.

K. Supowit and E. Reingold. The complexity of drawing trees nicely. Acta Informatica, 18(4):377-379, 1983.

J. Walker II. A node-positioning algorithm for general trees. Software - Practice and Experience, 20(7):685-705, 1990.

C. Wetherell and A. Shannon. Tidy drawings of trees. IEEE Transactions on Software Engineering, 5(5):514-520, 1979.