tree layouts: tidy, radial, hyperbolic, treemap
2026-06-30
the last three parts fought crossings. force-directed layouts (parts 1 and 2) jiggle nodes until the crossings settle down; the Sugiyama framework (part 3) spends a whole phase, the NP-hard one, just ordering nodes to cut crossings. trees make all of that disappear. a tree is planar by construction: there is exactly one path between any two nodes, no cycles, so you can always draw it on the plane with zero edge crossings. the layout problem stops being "how do i untangle this" and becomes "how do i pack this recursive structure so it reads cleanly and fits the space."
that is a different kind of problem, and it has a different kind of answer. where force-directed is a simulation and Sugiyama is a pipeline, tree layout is a recursion, and the canonical algorithm (Reingold-Tilford) is one of the most elegant linear-time results in the field. this part walks through it, then through three variants that reuse the same recursion in different geometries: radial trees in polar coordinates, hyperbolic trees in the Poincaré disk, and treemaps that throw out node-link drawing entirely and encode the hierarchy as nested area.
throughout, the reference implementation is d3/d3-hierarchy at commit c4ae7066. it is small, unusually well-commented, and implements every variant in this post.
the recursive layout idea
start with the obvious approach and watch it fail. to lay out a tree, lay out each subtree, then place the subtrees side by side and center the parent above them. it is a clean post-order recursion:
layout(node):
for each child: layout(child)
place the children's subtrees left to right, not overlapping
set node.x = midpoint of (first child.x, last child.x)
set node.y = node.depth
this produces a valid drawing. the trouble is what "place the subtrees side by side, not overlapping" means. the naive reading is "shift each subtree right until its bounding box clears the previous one." that wastes space badly. two subtrees can interlock: one leans right at the top, the other leans left at the bottom, and their bounding boxes overlap even though the actual nodes never would. you want to slide them together until the nodes almost touch, not until the boxes do.
so the real question is how close two adjacent subtrees can get. that depends only on their facing edges: the right contour of the left subtree and the left contour of the right one. the contour is the sequence of rightmost (or leftmost) nodes at each depth. to nest two subtrees tightly, walk both contours down level by level, find the level where they come closest, and shift the right subtree over by exactly that gap.
left subtree right subtree push them together until the
right contour left contour contours are one unit apart:
a d a d
\ / \ \ / \
b e f ---> b e f
\ / \ /
c g c g <- closest level
sets the gap
this is the heart of every tidy tree algorithm, and it is also where the naive version blows up. walking the full contour at every merge is O(n) per merge and O(n^2) over the tree, and deep skewed trees hit that worst case. Reingold and Tilford's 1981 paper is the trick that makes it linear.
reingold-tilford: tidy trees in o(n)
Reingold and Tilford first pinned down what "tidy" should mean, as a set of aesthetic constraints:
- nodes at the same depth sit on the same horizontal line.
- a parent is centered over its children.
- the order of children is preserved left to right.
- a subtree is drawn identically wherever it appears, so two isomorphic subtrees are congruent regardless of position.
- the drawing of a tree and the drawing of its mirror image are reflections of each other.
constraints 4 and 5 are the demanding ones. they rule out the cheap "just shift right" packing, because the same subtree would get drawn differently depending on what sits to its left. honoring them is what makes the output look hand-drawn rather than mechanical.
the algorithm earns O(n) with two ideas. the first is relative coordinates: instead of storing each node's absolute x, store a prelim (preliminary x within its subtree) and a mod (a modifier that every descendant inherits). when you shift a subtree right, you bump one mod at its root in O(1) instead of touching every node inside it. a second top-down pass sums the modifiers along each root-to-node path to recover absolute coordinates.
the second idea is threads. to walk a contour you need to follow it down past where a subtree's own children run out. Reingold-Tilford stitches a "thread" pointer from the bottom of a shorter contour across to the next subtree's contour, so a contour walk can skip from one subtree straight to the relevant node in the next without descending through everything in between. the threads turn the total contour-walking work across the whole tree into something linear rather than quadratic.
the 1981 paper handled binary trees. Walker (1990) generalized it to n-ary trees, but his version had a subtle case that degraded to O(n^2). Buchheim, Jünger, and Leipert (2002) fixed it, restoring true O(n) for general trees, and that corrected version is what d3 implements. the two passes are right there in the layout function: eachAfter(firstWalk) is the post-order pass that computes prelim and mod, and eachBefore(secondWalk) is the pre-order pass that sums the modifiers into final coordinates.
z is prelim and m is mod in d3's terse field names (the TreeNode constructor above documents them). read firstWalk as the recursion's combine step. by the time it runs on v, all of v's children already have preliminary positions, so midpoint is the center of the children and the node wants to sit there. if v has a left sibling w, it must also clear that sibling, so its preliminary x is w.z + separation(...), and the difference between that forced position and the natural midpoint is stored in m to be pushed down onto the children later. the real work is hidden in apportion, which is the contour walk: it threads down the inside contours of v's subtree and its left siblings, and wherever they would collide it calls moveSubtree to shift the offending subtree over, distributing the shift across any smaller subtrees caught in between so spacing stays even. that is the part Buchheim corrected, and it is why the whole thing stays linear.
radial trees: same recursion, polar coordinates
once you have the tidy recursion, you get radial trees almost for free. instead of mapping a node's position in its layer to an x-coordinate, map it to an angle, and map depth to radius. the root sits at the center, each level is a concentric ring, and the angular slice a subtree occupies is proportional to its breadth. the recursion is unchanged; only the final coordinate transform differs.
cartesian tidy tree radial tree
root . . .
/ \ . root .
a b . / \ .
/ \ / \ . a b .
c d e f . | | .
. c d e f .
. . . . .
x -> angle around the center
depth -> distance from the center
the one thing that does change is separation. in a Cartesian tree, sibling subtrees need the same horizontal gap no matter how deep they are. in polar coordinates, a fixed angular gap turns into a larger and larger arc length as the radius grows, so leaves on the outer rings drift apart while inner nodes crowd. d3 even leaves the fix in the source as a commented-out function: divide the separation by depth, so the angular spacing shrinks with radius and the arc-length spacing stays roughly constant. radial trees are the natural choice when the tree is bushy and roughly balanced, because the layout uses the full 360 degrees around the root instead of letting a wide tree sprawl off the right edge of the screen.
hyperbolic trees: focus and context
radial layout still runs out of room. the number of nodes at depth d in a branching tree grows exponentially, but the circumference of a ring in the Euclidean plane grows only linearly with radius. so the outer rings get exponentially more crowded, and a large tree turns into an unreadable smear at the rim. you can keep panning and zooming, but then you lose the context: you can see a leaf or the whole tree, never both.
hyperbolic trees, from Lamping, Rao, and Pirolli (1995), solve this with geometry. lay the tree out in the hyperbolic plane instead of the Euclidean one, then project that plane into a unit disk (the Poincaré disk model) for display. the key fact about the hyperbolic plane is that the circumference of a circle grows exponentially with its radius, which is exactly the growth rate of nodes by depth. the geometry has room for the tree because it expands at the same rate the tree does.
the Poincare disk: the whole infinite hyperbolic plane,
squeezed into a unit circle.
. - - - - - .
/ o o o \ nodes near the center: large, in focus
/ o O-o-O o \
| o / | \ o | the focused subtree gets most of the disk
| o o o o o |
\ o o o o / nodes near the rim: shrunk toward the
\ o o o o / boundary, but still visible for context
` - . _ . - '
the boundary circle is the horizon: infinitely far away
in hyperbolic distance, so there is always more room out there.
the payoff is focus plus context. whatever subtree you focus sits near the center of the disk and gets most of the space; everything else is compressed smoothly toward the boundary circle, shrinking but never vanishing. the rim is a horizon: in hyperbolic distance it is infinitely far away, so the disk holds the entire tree no matter how big. navigation is a Möbius transformation of the disk: grab any node, drag it toward the center, and the whole layout flows so that node into focus while the rest slides outward, all without ever recomputing the underlying layout. it is the original fisheye view for hierarchies, and it is still the right tool when the tree is too big to show at uniform scale but you want to keep the global shape in sight.
treemaps: when area encodes the data
every layout so far draws nodes and links. treemaps (Shneiderman, 1992) throw that out. the original motivation was mundane: Shneiderman wanted to see which files were eating an 80 percent full hard disk, and a node-link tree of the directory hierarchy wasted most of the screen on the links and told him nothing about size. so he made the area mean something.
a treemap takes a rectangle and recursively subdivides it. the root is the whole canvas. split it into pieces, one per child, with each piece's area proportional to that subtree's total value (file size, budget, population, whatever the leaves measure). then recurse into each piece with the same rule. the result is a space-filling map where every pixel belongs to some leaf, nesting shows the hierarchy, and area shows the magnitude. for "where did all the space go" questions it is unbeatable, because the big things are literally the big rectangles.
slice-and-dice: alternate the cut direction by depth
+-------------------------------+
| A | B | C | level 1: vertical cuts
| | | |
| +----------+ |
| | B2 | | level 2 inside B: horizontal cuts
| +----------+ |
| | B3 | |
+-------------------------------+
simple, stable, and it produces slivers: deep nodes
become long thin rectangles that are hard to compare.
Shneiderman's original subdivision was slice-and-dice: cut vertically at one level, horizontally at the next, alternating all the way down. it is dead simple and has one nice property, stability, in that small changes to the data only nudge rectangles slightly. but it produces terrible aspect ratios. a node with many descendants gets sliced into long thin slivers, and slivers are hard to see, hard to label, and hard to compare by eye. area is accurate but unreadable. that is the problem the next algorithm fixes.
squarify: the greedy heuristic
the readability of a treemap comes down to aspect ratio: rectangles close to square are easy to compare and label, long slivers are not. Bruls, Huijing, and van Wijk (2000) gave the greedy heuristic that almost every treemap uses today, including d3's default. it lays out the children of a rectangle one row at a time, and within a row it keeps adding rectangles as long as doing so keeps the worst aspect ratio in the row from getting worse. the moment adding the next rectangle would make the row's worst aspect ratio worse, it closes the row, lays it along the shorter side of the remaining space, and starts a fresh row in what is left.
the cleverness is the stopping test. you do not know in advance how many rectangles belong in a row. so you track the worst (largest) aspect ratio the current row would have, and you keep absorbing the next node while that worst ratio keeps improving or holding. as soon as it would degrade, you stop. greedily optimizing the worst case at each step gives rows that are all close to square, which is exactly what the eye wants.
the outer while lays out one row per iteration. minRatio is the best worst-case aspect ratio the row has achieved so far; the inner for keeps adding nodes and recomputing newRatio, and the instant newRatio > minRatio (the row got worse) it backs out the last node with sumValue -= nodeValue and breaks. minValue and maxValue track the smallest and largest node in the row because the worst aspect ratio is driven by the extremes, and alpha/beta are just the algebra that turns those values plus the current free rectangle into an aspect ratio without computing actual coordinates yet. once the row is fixed, row.dice = dx < dy orients it along the shorter side, treemapDice or treemapSlice positions the rectangles within the row, and the remaining free space shrinks by the row's value before the next iteration.
one detail worth noting: d3 defaults the ratio parameter to the golden ratio, not 1. you might expect the target aspect ratio to be a perfect square, but Bruls et al. observed that rectangles near the golden ratio read about as well and the slightly relaxed target produces a more stable, less fidgety layout when the data updates. squarify gives up the strict stability of slice-and-dice (reordering can reshuffle a row), but the readability win is large enough that it is the default everywhere.
reading the source: d3-hierarchy
d3-hierarchy is the cleanest place to read all of this end to end. it separates the data structure from the layouts: you build a hierarchy once, then hand it to whichever layout you want. at commit c4ae7066:
the data structure src/hierarchy/index.js (parent/child links,
eachBefore / eachAfter)
tidy node-link tree src/tree.js (Reingold-Tilford via
Buchheim et al.)
dendrogram / radial src/cluster.js (all leaves on one level)
treemap dispatcher src/treemap/index.js
squarify heuristic src/treemap/squarify.js
slice / dice / binary src/treemap/{slice,dice,binary}.js
the two traversal helpers on the hierarchy, eachAfter (post-order) and eachBefore (pre-order), are the whole reason tree.js reads as cleanly as it does: the algorithm is literally "post-order to compute preliminary positions, pre-order to resolve them," and those two methods are how it expresses the two walks. cluster.js is worth a read right after tree.js for contrast: it is the dendrogram layout that puts every leaf on the same final level (the look you want for phylogenetic trees and hierarchical clustering), and switching it between Cartesian and radial is the same angle-versus-x transform described above. the treemap files are small and independent; squarify.js is the one to read, and the others (slice.js, dice.js, binary.js) are alternative subdivisions you can drop in via the same dispatcher.
radial and hyperbolic layouts are not separate algorithms in the source so much as separate coordinate transforms applied to the same recursion, which is the real lesson of this part: the tidy recursion is the engine, and the geometry you project it into is a choice you make at the very end.
papers to read next
Reingold, E. M., and Tilford, J. S. (1981). "Tidier Drawings of Trees." IEEE Transactions on Software Engineering SE-7(2), pp. 223-228. DOI: 10.1109/TSE.1981.234519. the foundational paper, and still the clearest statement of what "tidy" means. it handles binary trees, and the aesthetic constraints it lays out (especially "isomorphic subtrees are drawn congruently") are the spec every later algorithm implements. short and readable; start here.
Buchheim, C., Jünger, M., and Leipert, S. (2002). "Improving Walker's Algorithm to Run in Linear Time." Graph Drawing 2002, Springer LNCS 2528, pp. 344-353. DOI: 10.1007/3-540-36151-0_32. the version d3 actually implements. Walker generalized Reingold-Tilford to n-ary trees in 1990 but his algorithm had a case that ran in O(n^2); this paper finds and fixes it. read it for the threads-and-modifiers machinery and the apportion procedure, which is the part of tree.js that rewards study.
Lamping, J., Rao, R., and Pirolli, P. (1995). "A Focus+Context Technique Based on Hyperbolic Geometry for Visualizing Large Hierarchies." CHI 95, pp. 401-408. DOI: 10.1145/223904.223956. the hyperbolic tree. the geometry is doing the heavy lifting, and the paper explains the Poincaré disk model and the Möbius navigation more gently than a geometry textbook would. worth it even if you never build one, for the idea that matching your layout space's growth rate to your data's growth rate is a design lever.
Bruls, M., Huizing, K., and van Wijk, J. J. (2000). "Squarified Treemaps." Data Visualization 2000, Springer, pp. 33-42. DOI: 10.1007/978-3-7091-6783-0_4. the squarify heuristic, in four pages with the pseudocode you just read in JavaScript. it also has the honest discussion of the stability-versus-aspect-ratio tradeoff that explains why slice-and-dice did not simply disappear. pair it with Shneiderman's original 1992 treemap paper (DOI: 10.1145/102377.115768) for the motivation.
next: part 5 leaves these clean recursive structures behind for the layouts that treat the graph as a matrix. spectral methods position nodes using the eigenvectors of the graph Laplacian, and constraint-based layouts let you bolt hard requirements (alignment, non-overlap, fixed positions) onto an otherwise free optimization.