How Mermaid Draws Diagram Without Crossing Arrows?
The Sugiyama Framework
| Untangling a graph | VLSI Connections | ~12 Min Read |
One afternoon, while working through a straightforward CPU subsystem consisting of a CPU, GIC, interconnect, and several peripherals including UART, memory, and Ethernet, I decided to generate a datasheet showing the platform's interfaces and connectivity.The SystemC description was remarkably clear. The structure flowed naturally, and anyone reading the platform configuration could understand the architecture almost instantly.
Then I asked a tool to draw it.What emerged was a diagram far more complicated than the design itself. Connections crossed where they didn't need to. Router outputs twisted around each other. A return path sliced diagonally across the page, cutting through unrelated connections. The architecture hadn't changed, but its visual representation had become harder to understand than the source description.
The netlist remained clean. The diagram did not.
And that raised an interesting question: why is laying out a block diagram often harder than building the system it represents?
Those of us who build systems have been drawing block diagrams for SoCs and platforms for as long as there have been SoCs and platforms. What has changed is how we produce them. In the age of AI we do not open a drawing canvas anymore. We describe the structure in text, as Graphviz dot or as Mermaid, and hand it to a tool that lays it out for us. The tool does the placing, the routing, and the connecting. And here is the part that stopped me: it does all of that using a body of principles that most of us who lean on it every day have never actually looked at. We treat the layout as free. It is not. Unravelling what the tool is silently doing on our behalf is one of the goals of this post.
Because the obvious question is: why does a tool this mature struggle with something that looks so visual and so obvious? Surely it could just try different arrangements until it lands on the one with no crossings?
The answer turns out to involve a problem that has occupied graph theorists since the 1970s, that is NP-hard in its general form, and that is solved by the very same family of algorithms that route the wires on the chips I was building the diagram to verify. I went in mildly annoyed at my tool. I have not fully climbed back out of the rabbit hole since.
The Puzzle, Stated Visually
Before any theory, it helps to see the problem in its rawest form. Forget the CPU subsystem for a moment and take something small enough to hold in your head: six nodes, labelled A through F, connected by seven edges. A goes to C and D. B goes to C and E. C and D both feed F. E feeds F as well. That is the entire graph. You could sketch it on the back of a napkin.
Now draw it. If you drop the six nodes at more or less arbitrary positions and connect them with straight lines, you get a knot: several of those seven edges cross one another, and the picture tells you almost nothing about the structure. So here is the puzzle. Is there an arrangement of these six nodes that produces zero crossings? Sit with it for a second before scrolling. For a graph this small the answer feels like it should be easy to find by eye, and that intuition is exactly the thing this post is going to complicate.
Why This Is Hard
The tempting strategy is brute force: try every arrangement, keep the best one. The problem is how fast the number of arrangements grows. If you have organized your nodes into layers, and a single layer holds n nodes, then that one layer alone has n factorial possible orderings. For 10 nodes in a layer that is 3,628,800 orderings. For 15 it is over a trillion. And a real diagram has many layers, each multiplying the others. The search space does not merely get large, it detonates.
You might hope this is just a case of nobody having found the clever shortcut yet. It is not. Even in the stripped-down case of only two layers, deciding the ordering that minimizes crossings is NP-hard, a result established in the classical graph-drawing literature. In plain terms: there is no known algorithm that is guaranteed to find the perfect arrangement in reasonable time, and strong theoretical reasons to believe none exists. Every diagram tool you have ever used, Mermaid, Graphviz, all of them, is therefore running an approximation. When your arrows come out crossed, you are looking at a heuristic that did its best and stopped.
It helps to pin down what a crossing actually is, because the definition is more mechanical than the visual tangle suggests. Take two layers, one above the other, and two edges running between them, one from u to v and one from x to y. Those two edges cross if and only if their endpoints interleave: u sits before x in the upper layer, but v sits after y in the lower one. That is the whole condition. Crossing minimization, stripped of its visual drama, is a counting problem over pairs of edges between adjacent layers, and the widget below lets you feel that counting happen as you move nodes around.
The outer nodes (A, B and C, D) are fixed. Only the four numbered nodes in the middle can be reordered — drag them, or step the search below.
Four nodes means 4! = 4×3×2×1 = 24 possible orderings. Brute force can check all 24 in a blink. Add nodes and it detonates: 5 nodes give 120, 10 nodes give 3,628,800.
Interactive crossing counter: drag the four numbered middle nodes to reorder them, or step through the 24 brute-force orderings to find the minimum crossings.
The Sugiyama Framework
In 1981, Kozo Sugiyama, Shojiro Tagawa, and Mitsuhiko Toda published a paper in IEEE Transactions on Systems, Man, and Cybernetics with the modest title "Methods for Visual Understanding of Hierarchical System Structures." It laid out a four-phase pipeline for drawing directed graphs that, more than four decades later, still underpins virtually every serious diagram tool. When Mermaid lays out your flowchart, its default engine, dagre, is running a JavaScript implementation of this framework. Graphviz's dot algorithm is another implementation of the same idea. The Eclipse Layout Kernel, ELK, is a more modern descendant that Mermaid can also be pointed at for harder diagrams.
The four phases are cycle removal, layer assignment, crossing minimization, and coordinate assignment, run in that order. Each one is an independent algorithmic problem, and each has its own NP-hard worst case with its own family of practical shortcuts. The genius of the paper was not any single algorithm inside a phase. It was the decomposition itself. By breaking one intractable problem into four smaller problems and solving each one "well enough" in sequence, you get a layout that is good enough to read for the graphs that actually turn up in real work. What follows is a walk through each phase, with the same principles the tool applies silently laid out where you can see them.
Phase 1: Cycle Removal
The framework's later phases all assume the input is a directed acyclic graph, one where you can walk the arrows forward and never return to where you started. Real graphs rarely oblige. A feedback path in a SystemC model, a loop in a state machine, a mutually recursive pair of build targets: cycles are everywhere, and the very first thing the pipeline has to do is get rid of them.
It does this by temporarily reversing a small set of edges so that no cycle survives. Choosing the smallest such set is the Feedback Arc Set problem, and in its general form it is NP-hard, so once again the tool reaches for a heuristic rather than an exact answer. For the sparse, shallow graphs that block diagrams tend to be, a greedy approach works well: walk the graph depth-first, and whenever you find an edge pointing back to a node you are still in the middle of visiting, reverse it. That single edge was the one closing a loop, and flipping it breaks the loop without disturbing the rest of the structure.
The reversed edges are not thrown away. The pipeline remembers them, lays the graph out as though they pointed the "wrong" way, and then in the final drawing flips them back to their true direction, usually rendered as a curved arrow running against the general flow. This is why a well-drawn state machine can show its feedback transitions as graceful backward loops instead of chaos: the loop was cut for the duration of the layout, then quietly stitched back in.
Two separate cycles here, so one reversal is not enough. Click an edge to reverse it, or step the greedy heuristic to fix one back edge at a time.
Interactive cycle breaker with two separate cycles: click an edge to reverse it, or step the greedy heuristic to reverse one back edge per click until the graph is acyclic.
Phase 2: Layer Assignment
With a cycle-free graph in hand, every node gets assigned to a horizontal layer, sometimes called a rank, with one rule: every edge must point from a lower-numbered layer to a higher-numbered one. This is what turns a shapeless graph into something with a clear top-to-bottom flow. The simplest way to do it is the longest-path method: put each node at a layer one greater than the deepest of its predecessors, so sources land in layer 0 and everything else settles as early as its dependencies allow. It is fast, it guarantees every arrow points forward, and it keeps the number of layers as small as possible.
The complication is edges that reach across more than one layer. Suppose a node in layer 0 connects directly to a node in layer 3. That single edge now has to travel across layers 1 and 2, and the later phases have no clean way to reason about an edge that skips levels. The fix is a small piece of sleight of hand: insert a chain of invisible placeholder nodes, one in each layer the edge passes through, and route the long edge through them. An edge from A in layer 0 to F in layer 3 becomes A to dummy1 to dummy2 to F, four short single-layer hops instead of one long jump.
These dummy nodes are not just bookkeeping. They take part in the next phase exactly as real nodes do, competing for position and pushing other nodes around, which is precisely what makes the final edge route bend smoothly rather than slicing straight through whatever lies between its endpoints. In the finished drawing they vanish, leaving behind only the waypoints that the edge quietly bends around. The widget below lets you watch layers fill up step by step and see a dummy node appear the moment an edge is stretched across more than one level.
All seven nodes start unassigned. The longest-path method places each node one layer deeper than its deepest predecessor. Press step to begin.
Interactive layer assignment: step through the longest-path algorithm placing nodes into layers, then watch a dummy node appear on the edge that spans two layers.
Phase 3: Crossing Minimization
This is the heart of the whole thing, and the phase that was quietly torturing my CPU subsystem diagram. Every node now sits in a layer, but the order of nodes within each layer is still up for grabs, and that ordering is what decides how many edges cross. The problem shrinks to a clean question asked once per pair of adjacent layers: given these two rows of nodes, what ordering minimizes the crossings between them? This is the bipartite crossing number problem, and as noted earlier it is NP-hard even in this two-layer form. So the pipeline does not solve it. It approximates it, well.
The workhorse heuristic is the barycenter method, and its intuition is almost physical. For each node in one layer, look at its neighbors in the adjacent fixed layer and compute their average position. That average, the barycenter, is where the node "wants" to sit, right in the middle of the things it connects to. Sort the nodes in the layer by their barycenters and you pull each one toward its neighbors, which tends to straighten the edges between the two layers. Then flip direction and do it again, letting the layer you just fixed drive the ordering of the one beside it. The sweep runs back and forth, layer by layer, until a pass produces no further improvement.
Barycenter sweeps are fast but a little myopic; they can settle into an ordering that is good but not quite locally optimal. So a second, finer heuristic rides alongside it: the transpose step. After a sweep, walk through each layer and, for every adjacent pair of nodes, try swapping them. If the swap lowers the crossing count, keep it; if not, put them back. This is pure local search, and it catches the small stubborn tangles that the barycenter average glides past.
Neither step promises the true minimum, and neither needs to. Alternating barycenter sweeps with transpose passes converges quickly in practice, typically within a few dozen iterations even on real-world graphs, and lands on a layout that is almost always good enough to read. When it does not quite reach zero, that is not a bug. It is the visible edge of an NP-hard problem, and the tool declining to spend the rest of the afternoon chasing an arrangement that may not exist.
Phase 4: Coordinate Assignment
By now the hard combinatorial work is done. Every node knows which layer it belongs to and where it sits in that layer's ordering. The last phase turns those abstract positions into real pixel coordinates. One axis is trivial: every node in the same layer shares the same coordinate along the flow direction, so the layers line up as clean rows. The other axis is where the remaining judgment lives. Nodes are nudged along it to shorten edges and reduce the number of bends, while keeping enough space that no two nodes overlap. The common approach, often the Brandes-Köpf method, balances each node against pulls from the layers above and below until the whole drawing settles into something straight and evenly spaced.
This is also where the earlier sleight of hand pays off. The dummy nodes inserted back in phase 2 become the waypoints that long edges bend through, so a wire spanning several layers arcs smoothly around whatever lies in its path instead of cutting across it. And the edges reversed in phase 1 are finally flipped back to their true direction and drawn as gentle curves running against the flow, the visible scar of the cycles that had to be cut. What comes out the far end is the diagram you actually see: rows of aligned nodes, edges that bend rather than slice, and feedback loops that read as loops. Four tractable problems, solved in sequence, adding up to something that looks like it was arranged by hand.
The VLSI Connection
Here is where the rabbit hole opened all the way up. The problem of minimizing crossings in a block diagram is not merely similar to a problem in chip design. It is structurally the same problem, wearing the vocabulary of a different field. On the hardware side it is called channel routing, and it is one of the oldest problems in VLSI physical design.
A channel is a rectangular strip of the chip bounded above and below by two rows of pins. Each net, a named connection between pins, has to be assigned to a horizontal track running along the channel. Two nets cannot share a track if their horizontal spans overlap, because their wires would collide. The goal is to connect everything using as few tracks as possible, since fewer tracks means a shorter channel and a smaller chip. Swap a few words and this is the layer-ordering problem from phase 3: tracks are the orderings, nets are the nodes, and a track conflict is a crossing.
The correspondence is not loose analogy, it is captured by two graphs that the router builds explicitly. The Horizontal Constraint Graph connects any two nets whose spans overlap, meaning they cannot occupy the same track; the minimum number of tracks is bounded below by the largest clique in that graph, which is itself NP-hard to find exactly. The Vertical Constraint Graph captures ordering: if a pin on the top row and a pin on the bottom row must connect through the same column, one net is forced above the other, and a cycle in this graph means the channel simply cannot be routed as drawn without an escape hatch. Line these up against the graph-drawing phases and they match part for part: the HCG clique is the width of a layer, a VCG cycle is a Sugiyama back-edge, a track is a layer, a net is a node, and the via you insert to break an unroutable VCG cycle is the dummy node you insert to route a long edge. The Yoshimura-Kuh channel router, published in 1982, and the greedy channel routers of the same year are direct contemporaries of the Sugiyama paper, three groups of people solving one problem from two directions without, as far as I can tell, ever quite noticing they were the same.
That is the thread the widget below pulls on. Toggle between the graph view and the channel view and you are looking at a single underlying structure rendered two ways. Reorder the nodes and watch the tracks rearrange to match. The picture changes; the constraints do not.
Drag a bottom node left or right to reorder it. Both views show one structure. Crossings: 0
Interactive comparison of a graph crossing problem and a VLSI channel routing problem. Drag a bottom terminal and watch nodes glide into place; both views stay in sync.
A Minimal C++ Implementation
Theory is easier to trust when you can run it. The full program walks the entire pipeline on a single ten-node directed graph that deliberately contains a cycle, so every stage has real work to do: it detects and reverses the back edge, assigns layers by longest path, inserts dummy nodes for long edges, and minimizes crossings with alternating barycenter sweeps and transpose passes, printing an ASCII picture of the graph at each step. It is written to line up one-to-one with the phases above, so you can read a function and point to the paragraph it came from. Rather than paste all six hundred lines, here are the pieces that matter, each tied to a phase you have already seen. The button below compiles and runs the whole thing in your browser.
Phase 1 is the greedy loop: find a back edge, reverse it, repeat until none remain.
void remove_cycles(Graph& g) {
while (auto back = find_one_back_edge(g)) {
int fu = back->first, fv = back->second;
for (auto& e : g.edges) {
if (e.from == fu && e.to == fv && !e.reversed) {
std::swap(e.from, e.to); // reverse direction
e.reversed = true;
break;
}
}
}
}Phase 2 assigns each node to one layer past its deepest predecessor, then splits any edge that spans more than one layer into a chain through dummy nodes.
for (int v : adj[u]) {
layer[v] = std::max(layer[v], layer[u] + 1);
if (--indeg[v] == 0) newly.push_back(v);
}
// ... later, for each edge u->v with layer(v) - layer(u) > 1:
int prev = e.from;
for (int L = lu + 1; L < lv; ++L) {
int d = next_id++; // a dummy node in layer L
lg.edges.push_back({prev, d});
prev = d;
}
lg.edges.push_back({prev, e.to}); // final hop into vPhase 3 counts crossings the fast way. Sort the edges by source position, read off the destination positions, and the number of crossings is exactly the number of inversions in that sequence, which merge sort counts in O(E log E).
int count_crossings(const LayeredGraph& lg, int layer_idx) {
std::vector<std::pair<int,int>> segs;
for (const auto& e : lg.edges)
if (lg.layer_of[e.from] == layer_idx &&
lg.layer_of[e.to] == layer_idx + 1)
segs.push_back({lg.pos[e.from], lg.pos[e.to]});
std::sort(segs.begin(), segs.end()); // by source, ties by dest
std::vector<int> dst;
for (auto& s : segs) dst.push_back(s.second);
return (int) count_inversions(dst); // merge-sort inversion count
}And the barycenter sweep itself: give each node the mean position of its neighbors in the fixed layer, then sort the layer by that value, breaking ties stably.
double bary = (cnt > 0) ? sum / cnt
: (double) lg.pos[node];
keyed.push_back({bary, node});
// ...
std::stable_sort(keyed.begin(), keyed.end(),
[](const auto& a, const auto& b){ return a.first < b.first; });Run it and the graph tells its own story, stage by stage, ending in a clean layered layout. Here is the tail of the output, the minimized result after cycle removal, layering, and crossing minimization have all run:
Run it and the graph tells its own story, stage by stage. It starts with a cycle, so cycle removal has to fire; layering then stretches long edges across eight layers, inserting twenty invisible dummy nodes to carry them; and crossing minimization brings the tangle down from twenty crossings to seven. Not zero, because for this graph zero is not reachable, which is exactly the point: the tool returns the best arrangement it can find, quickly, rather than chasing a perfect one that may not exist. Here is the shape of the run:
INPUT: a 10-node directed graph (16 edges)
edges: 0->2 0->3 1->3 1->4 2->5 3->5 3->6 4->6 5->7
6->7 6->8 7->9 8->9 2->6 0->5 8->3
Cycle present? yes
STEP 1 - cycle removal: reverse back edges to obtain a DAG
reversed edges: 6->3 (originally 3->6)
cycle present now? no
STEP 2 - layer assignment (longest path) + dummy nodes
layers: 8, dummy nodes inserted: 20
STEP 3 - crossing minimization (barycenter sweeps + transpose)
before: crossings = 20
after: crossings = 7The full run prints an ASCII picture of the graph at every stage, from the raw cyclic input through the minimized layout. Press the button above to watch all eight layers resolve in your browser.
What Mermaid Actually Does
Step back and the shape of the journey is a little funny. Arranging some boxes so their arrows do not cross feels like it should be trivial, the kind of thing you would knock out with a bit of trial and error. Instead it turns out to brush up against NP-hardness at nearly every phase: the feedback arc set you cut to remove cycles, the crossing count you fight in the middle, the clique that bounds a channel's width. The real gift of the Sugiyama framework was never a single clever algorithm. It was the decision to stop trying to solve the whole thing at once, and to break it into four smaller problems, each of which a fast, imperfect heuristic can handle well enough.
That is exactly what your tools are doing when you are not looking. Mermaid's default engine, dagre, is a Sugiyama implementation built around barycenter crossing minimization, and it assumes you have handed it something acyclic to begin with. Point Mermaid at its ELK backend and you get a more elaborate crossing-minimization stage for the diagrams that dagre struggles with. Graphviz's dot is the same framework again. None of them promises a crossing-free result, because for a general graph that promise cannot be kept. They promise a good-enough arrangement, quickly, and most of the time that is what readable means.
So the next time a Mermaid diagram hands you a crossed-arrow mess, it is worth remembering what just happened on your behalf. The layout engine ran a lineage of algorithms reaching back to a 1981 paper, algorithms whose cousins route the wires on the very chips you might be drawing the diagram to describe. We describe the structure in text now and let the machine place it, and it has been quietly applying these principles the whole time, whether or not we ever went looking for them. The abstraction layers could not look more different. The constraint graph underneath is the same.
Comments
Post a Comment