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. [Preprint]

WarningThere is a more recent version of this item available.

[img] Other
82Kb

Abstract

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:Preprint
Classifications:P Styles > P.720 Straight-line
M Methods > M.900 Tree
ID Code:12
Alternative Locations:http://e-archive.informatik.uni-koeln.de/431/

Available Versions of this Item

Repository Staff Only: item control page

References

Reingold, Edward M. and Tilford, John S. (1981) Tidier drawings of trees. IEEE Transactions on Software Engineering, 7 (2) 223-228.

Schieber, Baruch and Vishkin, Uzi (1998) 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, pp. 111-123. Springer Verlag.

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

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