Overview
Reingold-Tilford layout assigns x-coordinates to tree nodes using subtree contours, shifts overlapping subtrees apart, and recenters each parent over its children.
CoreSource checked
Reingold-Tilford Tree Layout
Draws tidy rooted trees by positioning subtrees recursively while separating their contours.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Intermediate
- Family
- Graph Drawing
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
Core Concepts
tree drawinggraph drawingforce layoutrecursiongraph traversal
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O((V + E) log V)
Worst
O(V^2 + E)
Space
O(V + E)
When to Use
- Use for compact, readable drawings of rooted trees.
- Use when sibling order should be preserved and subtrees should not overlap.
When Not to Use
- Avoid for general graphs that are not trees unless a tree has been extracted.
- Avoid when edge lengths or geometric constraints matter more than tidy hierarchy.
What It Does
- Computes graph drawing within Graph Drawing workloads (O((V + E) log V) time, O(V + E) space).
- Works by Draws tidy rooted trees by positioning subtrees recursively while separating their contours.
- Maintains key invariants across tree drawing, graph drawing, force layout.
Use Cases
- Production and research workloads requiring graph drawing via Draws tidy rooted trees by positioning subtrees recursively while separating their contours.
- Graph Drawing pipelines where O((V + E) log V) time and O(V + E) space fit system constraints.
- Engineering comparisons against Fruchterman-Reingold Layout and Sugiyama Layered Drawing when tuning graph drawing.
Inputs
- Graph G = (V, E) or rooted tree T
- Viewport bounds and spacing parameters
Outputs
- 2D vertex coordinate map (x_v, y_v) minimizing crossings or force energy
Pseudocode
- 1.Process children recursively in postorder
- 2.Place each child subtree beside the previous one
- 3.Shift subtrees apart using contour separation
- 4.Center the parent above its children
- 5.Accumulate modifiers in preorder to get final coordinates
Canonical Example
- Input
- root R with children A and B, and A has children C and D
- Output
- R centered above A and B; A centered above C and D
- Explanation
- Each subtree is placed tidily first, then shifted so sibling contours do not overlap.
Implementation Notes
- Run a postorder pass to compute preliminary positions and modifiers.
- Compare left and right contours to separate adjacent subtrees.
- Run a preorder pass to accumulate modifiers into final coordinates.
Common Pitfalls
- Different subtree depths require contour comparisons at each level.
- Parent centering must happen after children are shifted.
- Large labels need spacing based on label width, not only node count.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow placing subtrees recursively while keeping sibling contours separated on a small tree drawing example.
Step 1 of 5: Process children recursively in postorder
graph-traversal-mechanismNotes
The layout is for rooted trees; label sizes and orientation choices affect the final drawing.
Sources (2)
What each reference supports for this entry.
Handbook of Graph Drawing and Visualization
BookGraph drawing reference for Reingold-Tilford Tree Layout's layout objective, drawing constraints, and visual graph model.
Open sourceReingold-Tilford Tree Drawings
PaperOriginal reference for tidy layered drawings of rooted trees.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
UsesFruchterman-Reingold Layout
Graph Traversal · Core
Reingold-Tilford Tree Layout uses Fruchterman-Reingold Layout as a subroutine, representation, or supporting idea while placing subtrees recursively while keeping sibling contours separated.
Compare with thisRelationships
View full relationship pageReingold-Tilford Tree Layout uses Fruchterman-Reingold Layout as a subroutine, representation, or supporting idea while placing subtrees recursively while keeping sibling contours separated.
Reingold-Tilford Tree Layout uses Sugiyama Layered Drawing as a subroutine, representation, or supporting idea while placing subtrees recursively while keeping sibling contours separated.
Reingold-Tilford Tree Layout uses Walker Tree Layout as a subroutine, representation, or supporting idea while placing subtrees recursively while keeping sibling contours separated.
Related Algorithms
Tags
GraphTraversalDivide and Conquer