tree layouts: tidy, radial, hyperbolic, treemaptree layouts: tidy, radial, hyperbolic, treemap

parts 1 to 3 were all about fighting crossings. trees don't have that problem. a tree has no loops and exactly one path between any two nodes, so it can always be drawn with no crossings at all.

the question changes from "how do I untangle this" to "how do I pack this neatly so it's easy to read and fits the space". this post covers the classic answer (Reingold-Tilford), three variations on it, and treemaps, which skip the lines entirely.

the simple ideathe simple idea

draw a tree from the bottom up:

   layout(node):
     lay out each child's subtree
     place those subtrees side by side, without overlap
     put the node centered above its children

that works. the trouble is "side by side, without overlap". the easy version is to push each subtree right until its bounding box clears the previous one. but subtrees have uneven shapes: one might be wide at the top, the next wide at the bottom. their boxes collide even though their nodes never would, and the tree ends up much wider than it needs to be.

the better version compares the actual edges of the two subtrees. the right edge of the left subtree is its rightmost node on each level. the left edge of the right subtree is its leftmost node on each level. walk down both, level by level, and slide them together until the closest level is exactly one gap apart.

   left subtree     right subtree        slid together:

       a                  d                    a       d
        \                / \                     \     / \
         b              e   f       --->          b   e   f
          \            /                           \ /
           c          g                             c g   <- closest level

reingold-tilford: doing it fastreingold-tilford: doing it fast

sliding subtrees by their edges is the heart of every tidy tree algorithm. done naively, it gets slow on deep, lopsided trees, because you keep re-walking the same edges.

Reingold and Tilford (1981) first wrote down what "tidy" should mean:

1. nodes at the same depth sit on the same row.
2. a parent is centered over its children.
3. children stay in their original order.
4. identical subtrees are drawn identically, wherever they are.
5. a mirrored tree is drawn as a mirror image.

then they made it fast with two tricks:

• move a whole subtree in one step. instead of updating every node when a subtree shifts, store the shift once at the subtree's root. a final top-down pass adds up the shifts to get real positions.
• shortcuts along the edges. when one subtree is shorter than its neighbor, a pointer (a "thread") jumps from its bottom straight to the next subtree's edge. walking edges never re-does work.

together, that makes the whole layout run in time proportional to the number of nodes. the 1981 paper handled binary trees. Walker (1990) extended it to any number of children but had a slow case. Buchheim, Jünger and Leipert (2002) fixed that, and theirs is what d3 uses.

radial treesradial trees

take the tidy layout and read it differently: horizontal position becomes an angle, and depth becomes the distance from the center. the root sits in the middle, and each level is a ring around it. nothing about the method changes, only the last step.

   regular tidy tree          radial tree

        root                          . . .
       /    \                      .    root   .
      a      b                    .    /    \   .
     / \    / \                  .   a        b  .
    c   d  e   f                  .  |        |  .
                                   . c d    e f .
                                      . . . . .

one adjustment: a fixed angle between siblings is a small gap near the center but a big gap on the outer rings. so spacing is scaled down with depth to keep gaps even.

radial trees are good for bushy, balanced trees, since they use the space all the way around the root instead of sprawling off to one side.

hyperbolic treeshyperbolic trees

radial trees still run out of room. each level of a tree can have many times more nodes than the last, but each ring is only a little bigger than the one inside it. the outer rings get crowded fast.

hyperbolic trees (Lamping, Rao and Pirolli, 1995) fix this with a different kind of space. in hyperbolic geometry, there's much more room as you move outward, growing just as fast as the tree does. then that space is squeezed into a circle to display it:

          . - - - - - .
        /  o   o   o    \      near the center: big, in focus
      /  o  O-o-O  o      \
     |  o  /  |  \  o      |
     | o  o   o   o  o     |
      \  o   o    o  o    /     near the edge: small, but still visible
        \  o  o  o  o   /
          ` - . _ . - '

whatever you focus on sits in the middle and gets most of the space. everything else shrinks toward the edge but never disappears. click a node and the whole picture flows until that node is in the middle. you see the detail and the overall shape at the same time.

here are all of these on one 22-node tree. compare "bounding boxes" with "tidy" first, then open the hyperbolic view and tap around:

treemapstreemaps

every layout so far draws dots and lines. treemaps (Shneiderman, 1992) drop the lines. Shneiderman wanted to see what was filling up his hard disk, and a tree diagram of folders told him nothing about size.

so in a treemap, each node is a box, and its area is its size. the whole rectangle is the root. split it into one piece per child, sized by value, then split each piece the same way. big things are literally the big boxes.

the original way to split was slice-and-dice: cut vertically at one level, horizontally at the next, and so on.

   +-------------------------------+
   |   A    |    B     |     C      |   level 1: vertical cuts
   |        +----------+            |
   |        |    B2    |            |   level 2: horizontal cuts
   |        +----------+            |
   |        |    B3    |            |
   +-------------------------------+

it's simple, and small data changes only nudge the boxes. but it makes long, thin slivers that are hard to see, label or compare.

squarify: keep the boxes squaresquarify: keep the boxes square

Bruls, Huizing and van Wijk (2000) fixed the slivers with a greedy rule, and it's what nearly every treemap uses today:

1. fill the space one row of boxes at a time, biggest values first.
2. keep adding boxes to the current row as long as that doesn't make the row's worst box more stretched.
3. the moment it would, close the row along the short side of the remaining space and start a new row.

since every row is kept as square as possible, the whole treemap comes out close to square boxes, which is exactly what the eye wants.

scrub through it below. the outlined boxes are the row being built, and the dashed box is the space left over. flip to slice-and-dice to compare:

squarify gives up some stability: a small data change can reshuffle a row. the readability win is worth it, which is why it's the default everywhere.

reading the source: d3-hierarchyreading the source: d3-hierarchy

d3-hierarchy (at commit c4ae7066) has every layout from this post. you build the tree data once, then hand it to whichever layout you want:

   the tree data          src/hierarchy/index.js
   tidy tree              src/tree.js              (Buchheim et al.)
   dendrogram / radial    src/cluster.js           (all leaves on one row)
   treemaps               src/treemap/index.js
   squarify               src/treemap/squarify.js
   slice / dice / binary  src/treemap/{slice,dice,binary}.js

the tidy tree. firstWalk runs bottom-up and places each node relative to its subtree. z is the node's tentative x, and m is the shift passed down to its children later. apportion is the edge-walking that slides subtrees together:

function firstWalk(v) {
  var children = v.children,
      siblings = v.parent.children,
      w = v.i ? siblings[v.i - 1] : null;
  if (children) {
    executeShifts(v);
    var midpoint = (children[0].z + children[children.length - 1].z) / 2;
    if (w) {
      v.z = w.z + separation(v._, w._);
      v.m = v.z - midpoint;
    } else {
      v.z = midpoint;
    }
  } else if (w) {
    v.z = w.z + separation(v._, w._);
  }
  v.parent.A = apportion(v, w, v.parent.A || siblings[0]);
}

a second, top-down pass adds up the shifts to get final positions. that's the whole algorithm: bottom-up to place, top-down to resolve.

squarify. the outer while builds one row per loop. the inner for keeps adding nodes until the row's worst aspect ratio would get worse, then backs out the last one:

  while (i0 < n) {
    dx = x1 - x0, dy = y1 - y0;

    // Find the next non-empty node.
    do sumValue = nodes[i1++].value; while (!sumValue && i1 < n);
    minValue = maxValue = sumValue;
    alpha = Math.max(dy / dx, dx / dy) / (value * ratio);
    beta = sumValue * sumValue * alpha;
    minRatio = Math.max(maxValue / beta, beta / minValue);

    // Keep adding nodes while the aspect ratio maintains or improves.
    for (; i1 < n; ++i1) {
      sumValue += nodeValue = nodes[i1].value;
      if (nodeValue < minValue) minValue = nodeValue;
      if (nodeValue > maxValue) maxValue = nodeValue;
      beta = sumValue * sumValue * alpha;
      newRatio = Math.max(maxValue / beta, beta / minValue);
      if (newRatio > minRatio) { sumValue -= nodeValue; break; }
      minRatio = newRatio;
    }

    // Position and record the row orientation.
    rows.push(row = {value: sumValue, dice: dx < dy, children: nodes.slice(i0, i1)});
    if (row.dice) treemapDice(row, x0, y0, x1, value ? y0 += dy * sumValue / value : y1);
    else treemapSlice(row, x0, y0, value ? x0 += dx * sumValue / value : x1, y1);
    value -= sumValue, i0 = i1;
  }

one detail: d3 aims for the golden ratio instead of a perfect square. boxes near that shape read just as well, and the layout jumps around less when data changes.

radial and hyperbolic trees aren't separate algorithms in d3. they're the same tidy layout, with a different way of turning its output into screen positions.

papers to read nextpapers to read next

Reingold and Tilford (1981), "Tidier Drawings of Trees." the original, and still the clearest definition of "tidy". short. start here.

Buchheim, Jünger and Leipert (2002), "Improving Walker's Algorithm to Run in Linear Time." the version d3 uses.

Lamping, Rao and Pirolli (1995), "A Focus+Context Technique Based on Hyperbolic Geometry for Visualizing Large Hierarchies." the hyperbolic tree, explained gently.

Bruls, Huizing and van Wijk (2000), "Squarified Treemaps." squarify in four pages. pair it with Shneiderman's 1992 treemap paper for the backstory.

next: part 5 treats the graph as a matrix. spectral layouts get positions from linear algebra, and constraint-based layouts let you add your own rules.