Drawing Rooted Trees in Linear Time

Buchheim, Christoph and J√ľnger, Michael and Leipert, Sebastian (2006) Drawing Rooted Trees in Linear Time.
Published in: Software; Practice and Experience Vol. 36 (6). pp. 651-665.


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.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2005-483
Depositing User: Christoph Buchheim
Date Deposited: 03 Jun 2005 00:00
Last Modified: 08 Jul 2013 08:12
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/483