Premium
Drawing rooted trees in linear time
Author(s) -
Buchheim Christoph,
Jünger Michael,
Leipert Sebastian
Publication year - 2006
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.713
Subject(s) - computer science , time complexity , quadratic equation , extension (predicate logic) , graph , algorithm , state (computer science) , running time , degree (music) , theoretical computer science , mathematics , programming language , geometry , physics , acoustics
Abstract The aim of automatic graph drawing is the development of algorithms for creating nice and easily 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. 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. Copyright © 2006 John Wiley & Sons, Ltd.