Untangling graphs in 80 lines

Code Explorer renders type hierarchies, call graphs, and module dependencies as SVG diagrams. The first version used a grid layout: nodes in rows and columns, edges wherever they land. It looked like a bowl of spaghetti.

The proper solution is the Sugiyama algorithm, the standard for layered graph drawing since 1981. It sounds academic. Four phases, multiple papers, NP-hard subproblems. But a simplified version that skips the hard parts works surprisingly well for real code graphs.

Three steps

The full Sugiyama has a fourth phase (edge routing with dummy nodes for long edges) and solves the ordering problem optimally. We skip both. Bezier curves handle long edges well enough, and the barycenter heuristic gets close to optimal crossing reduction for the graph sizes we care about.

The trick that matters

Cycle breaking. Real code has cycles: A imports B, B imports A. Without handling this, layer assignment loops forever. DFS marks edges that point back up the call stack. We ignore those edges during layout but still draw them. The graph stays acyclic for the algorithm, visually complete for the user.

The barycenter heuristic is the other win. For each node, compute the average x-position of its neighbors one layer up (or down). Sort nodes in the layer by that average. Repeat in alternating directions. Four passes are enough. Most edge crossings vanish.

What we skip

The full algorithm inserts dummy nodes for edges that span multiple layers, routes edges around nodes, and solves an NP-hard optimization for crossing minimization. We skip all of that. Bezier curves handle multi-layer edges naturally, and the heuristic ordering is good enough for graphs under ~50 nodes, which covers every code visualization we render.

The entire layout function is 80 lines of TypeScript. No dependencies. It handles type hierarchies (parents on top, children below), call graphs (callers above callees), and module graphs (importers above imported). Same algorithm, three different visualizations, just by choosing which direction to pass the edges.