Reingold-Tilford Algorithm
A Reingold-Tilford Algorithm is a tree visualization algorithm.
- Context:
- It can be implemented in a Reingold-Tilford Tree Visualization System, such as http://bl.ocks.org/mbostock/4339184
- It can have a goal to make smarter use of space, maximize density and symmetry.
- It can be for binary trees - extended by (Walker, 1990) to cover general case, in turn enhanced by (Buchheim et al., 2006) to achieve a linear time.
- …
- Counter-Example(s):
- a Basic Recursive Tree-Drawing Algorithm that repeatedly divide space for subtrees by leaf count (Breadth of tree along one dimension; Depth along the other dimension) - which suffers from exponential growth of breadth.
- See: Tree Drawing, Tree Drawing System.
References
2014
- http://bl.ocks.org/mbostock/4339184
- The tree layout implements the Reingold-Tilford algorithm for efficient, tidy arrangement of layered nodes. The depth of nodes is computed by distance from the root, leading to a ragged appearance. Radial orientations are also supported. Implementation based on work by Jeff Heer and Jason Davies using Buchheim et al.'s linear-time variant of the Reingold-Tilford algorithm. Data shows the Flare class hierarchy, also courtesy Jeff Heer.
Compare to this radial layout.
- The tree layout implements the Reingold-Tilford algorithm for efficient, tidy arrangement of layered nodes. The depth of nodes is computed by distance from the root, leading to a ragged appearance. Radial orientations are also supported. Implementation based on work by Jeff Heer and Jason Davies using Buchheim et al.'s linear-time variant of the Reingold-Tilford algorithm. Data shows the Flare class hierarchy, also courtesy Jeff Heer.
2006
- (Buchheim et al., 2006) ⇒ Christoph Buchheim, Michael Jünger, and Sebastian Leipert. (2006). “Drawing Rooted Trees in Linear Time." Software: Practice and Experience 36, no. 6
- QUOTE: 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.
2002
- (Buchheim et al., 2002) ⇒ Christoph Buchheim, Michael Jünger, and Sebastian Leipert. (2002). “Improving Walker’s Algorithm to Run in Linear Time.” In: Graph Drawing, Springer Berlin Heidelberg. doi:10.1007/3-540-36151-0_32
- QUOTE: The algorithm of Walker (Walker, 1990) 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 clearly needs quadraticrun time. We explain the reasons for that and present a revised algorithm that creates the same layouts in linear time.
1990
- (Walker, 1990) ⇒ John Q. Walker. (1990). “A Node‐positioning Algorithm for General Trees." Software: Practice and Experience, 20(7). doi:10.1002/spe.4380200705
- QUOTE: Drawing a tree consists of two stages: determining the position of each node, and actually rendering the individuals nodes and interconnecting branches. The algorithm described in this paper is concerned with the first stage: given a list of nodes, an indication of the hierarchical relationship among them, and their shape and size, where should each node be positioned for optimal aesthetic effect?
This algorithm determines the positions of the nodes for any arbitrary general tree. It is the most desirable positioning with respect to certain widely-accepted heuristics. The positioning, specified in x, y co-ordinates, minimizes the width of the tree. In a general tree, there is no limit on the number of offspring per node; this contrasts with binary and ternary trees, for example, which are trees with a limit of two and three offspring per node. This algorithm operates in time O(N), where N is the number of nodes in the tree.
Previously, most tree drawings have been positioned by the sure hand of a human graphic designer. Many computer-generated positionings have been either trivial or contained irregularities. Earlier work by Wetherell and Shannon and Tilford, upon which this algorithm builds, failed to position the interior nodes of some trees correctly. The algorithm presented here correctly positions a tree's node using only two passes. It also handles several practical considerations: alternative orientations of the tree, variable node sizes and out-of-bounds conditions. Radack,3 also building on Tilford's work, has solved this same problem with a different algorithm which makes four passes.
- QUOTE: Drawing a tree consists of two stages: determining the position of each node, and actually rendering the individuals nodes and interconnecting branches. The algorithm described in this paper is concerned with the first stage: given a list of nodes, an indication of the hierarchical relationship among them, and their shape and size, where should each node be positioned for optimal aesthetic effect?
1983
- (Supowit & Reingold, 1983) ⇒ Kenneth J. Supowit, and Edward M. Reingold. (1983). “The Complexity of Drawing Trees Nicely." Acta Informatica 18, no. 4