C. Buchheim, M. Jünger, S. Leipert
Published in:
Software; Practice and Experience Vol. 36 (6). pp. 651-665
Abstract
The aim of automatic graph drawing is the development of algorithms for creating nice and well-readable layouts of abstractly given graphs. For the special case of rooted trees of unbounded degree, John Q. Walker II presented a drawing algorithm in this journal in 1990. This algorithm is an extension of the Reingold-Tilford algorithm. It yields very good results and is therefore widely used in practice. Furthermore, it is widely assumed to run in linear time, as the author claims in his article. However, the algorithm in its presented form clearly needs quadratic runtime. We explain the reasons for that and state a revised algorithm that creates the same layouts in linear time.