Drawing a graph that's too big to draw

Biological pathway maps are big. A single map can hold thousands of genes, compounds and reactions, and the questions people ask of them are interactive ones: where does this gene sit, what's connected to it, how does expression change along the path. They want to pan, zoom, hover and click, and they want the map to keep up.

Making large KEGG pathway maps fast enough to explore is one of the most satisfying problems I've worked on. Very little of the speed in work like this comes from a faster drawing library. It comes from drawing, checking and listening to far less, using a handful of techniques that apply to any big interactive visualisation.

1Stop comparing everything with everything

Drawing a map involves a lot of "does this overlap that?". Labels mustn't collide, nodes need room, and a click has to land on the right thing. The obvious way to answer is to compare every pair. For n items that's n(n − 1)/2 comparisons, so five thousand nodes means about twelve and a half million checks, every time anything moves.

A spatial index fixes this by remembering where things are. A quadtree splits the plane into four, then splits again wherever a square holds too many items. To find what overlaps a label, you look only in the squares that label touches, and most of the map is never examined. An R-tree does the same with nested bounding boxes and copes better with rectangles of very different sizes. Either way, the cost of a question stops depending on the size of the whole map.

2Labels that fit

Labels are where a dense map turns to noise first. A node is a few pixels across, but its name is fifty, so long before the nodes overlap, their labels do. Drawing every label produces a grey thatch that's worse than no labels at all, because it looks like information.

What works is greedy placement, in order of importance. Sort the nodes by how much they matter, which on a pathway map might be how connected a gene is, or whether it's in the user's results. Then, for each in turn, try a few spots around the node (right, left, above, below), take the first that doesn't collide with anything already placed, and drop the label if none is free. The collision test is a spatial-index query, so the whole pass is cheap enough to redo on every zoom, and that's the other half of the trick. Zoom in, and the same pass finds room for more labels, so detail arrives exactly when there's space to show it.

3When the network has no layout

KEGG maps arrive with coordinates, because someone drew them. Most networks don't, and laying one out usually means a force simulation: every node pushes every other node away, every edge pulls its two ends together, and the whole thing runs until it settles. The pulling is cheap, one force per edge. The pushing is the every-pair problem again: n² forces per step, for hundreds of steps.

The Barnes–Hut approximation answers it with the same quadtree. From far enough away, a crowded square of nodes pushes about as hard as a single heavy node at its centre of mass. So, for each node, walk the tree from the top. If a square is small compared with its distance, meaning its width divided by the distance is below a threshold called θ, treat the whole square as one body and stop. Otherwise, open it and look inside. Nearby nodes are counted one by one, distant crowds as a single sum, and a step costs about n log n instead of n². It's how d3's force layout works by default, with θ set to 0.9.

4Only draw what's on screen

The second technique sounds too obvious to mention, and it's skipped constantly: don't draw what nobody can see. At any moment the viewport shows a small part of a big map, and everything outside it can be skipped. Finding what's inside is, again, a spatial index query.

Zoomed out, the opposite problem appears. Everything is visible, but individual nodes are a pixel wide and their labels are unreadable smudges, so drawing them in full is pure cost. Level of detail means drawing a simpler version when the detail can't be seen: clusters instead of nodes, no labels below a legible size, short straight edges instead of every one. Zoom in and the detail returns, but by then most of the map is off screen.

5Canvas, SVG or WebGL

The choice of drawing surface matters less than everything above, but it sets the ceiling. SVG keeps every shape as an element in the page, which makes it easy to style, inspect and make accessible, and means every node is an object the browser must style, lay out and hold in memory. Canvas is a bitmap you paint with commands. It forgets each shape the moment it's drawn, so a shape costs nothing once it's painted, but hit testing and accessibility become your job, which is exactly where the spatial index earns its keep a second time. WebGL hands the painting to the GPU and copes with hundreds of thousands of points, at the price of shaders and of text drawn the hard way.

One canvas detail catches almost everyone. A canvas has a pixel size of its own, separate from the size it's displayed at, and on a high-density screen the default looks soft. The fix is to size the backing store by the device pixel ratio and scale the drawing to match:

const dpr = window.devicePixelRatio || 1;
canvas.width = Math.round(cssWidth * dpr);       // the pixels it really has
canvas.height = Math.round(cssHeight * dpr);
canvas.style.width = cssWidth + 'px';            // the size it's shown at
canvas.style.height = cssHeight + 'px';
ctx.setTransform(dpr, 0, 0, dpr, 0, 0);          // keep drawing in CSS pixels

The cost hides in the arithmetic. At a pixel ratio of 3, which is common on phones, a full-screen canvas has nine times as many pixels to fill as at 1. That's one more reason to draw less.

6One listener, not ten thousand

The last technique is about memory rather than speed. The easy way to make nodes interactive is to give each one its own event handler, a hover listener holding a closure over that node's data. With thousands of nodes that's thousands of objects, and if the map re-renders without removing the old handlers, every re-render adds thousands more. Memory climbs until something gives, and in a long-lived dashboard something always does.

Event delegation replaces all of them with a single listener on the container. When the pointer moves, that listener asks the spatial index which node is underneath, and shows the tooltip for that one. There's nothing per node left to leak, so memory stays flat however often the map redraws.

Tooltips are a classic place for leaks, because they're created and destroyed constantly and they hold references to the data they describe. I once diagnosed one in the tooltip rendering of a production Shiny dashboard. Fixing it cut the app's memory use by 90% and ended the disconnects its users had been hitting, and nobody had to change how they used it.

7Fast enough to stop noticing

There's a point in interactive work where speed stops being a feature and becomes the absence of friction. When a map answers in a few milliseconds, people stop waiting for it and start thinking with it. None of these techniques is new and none is clever. Together they're the difference between a visualisation people tolerate and one they actually use.