Drawing Non-Layered Tidy Trees In Linear Time - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Software: Practice and Experience Année : 2013

Drawing Non-Layered Tidy Trees In Linear Time

Résumé

The well-known Reingold-Tilford algorithm produces tidy-layered drawings of trees: drawings where all nodes at the same depth are vertically aligned. However, when nodes have varying heights, layered drawing may use more vertical space than necessary. A non-layered drawing of a tree places children at a fixed distance from the parent, thereby giving a more vertically compact drawing. Moreover, non-layered drawings can also be used to draw trees where the vertical position of each node is given, by adding dummy nodes. In this paper, we present the first linear-time algorithm for producing non-layered drawings. Our algorithm is a modification of the Reingold-Tilford algorithm, but the original complexity proof of the Reingold-Tilford algorithm uses an invariant that does not hold for the non-layered case. We give an alternative proof of the algorithm and its extension to non-layered drawings. To improve drawings of trees of unbounded degree, extensions to the Reingold-Tilford algorithm have been proposed. These extensions also work in the non-layered case, but we show that they then cause a $O(n^2)$ run-time. We then propose a modification to these extensions that restores the $O(n)$ run-time.

Dates et versions

hal-00923389 , version 1 (02-01-2014)

Identifiants

Citer

Atze van Der Ploeg. Drawing Non-Layered Tidy Trees In Linear Time. Software: Practice and Experience, 2013, 44 (12), pp.1467-1484. ⟨10.1002/spe.2213⟩. ⟨hal-00923389⟩

Collections

INRIA INRIA2
354 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More