TIL
Back

Layered Graph Drawing with the Sugiyama Framework

A layered drawing places vertices on parallel rows or columns and points most edges in one consistent direction. It fits dependency graphs, build pipelines, state machines, call graphs, and other directed structures where reachability matters more than geometric symmetry.

The Sugiyama algorithm turns a directed graph into this kind of hierarchy through a sequence of transformations. It temporarily breaks cycles, assigns vertices to discrete layers, inserts dummy vertices where edges skip layers, reorders each layer to reduce crossings, and finally chooses coordinates and edge routes. The result emphasizes the graph's overall direction while trying to keep edges short, straight, and easy to follow.

Sugiyama, Tagawa, and Toda introduced the method in 1981.1 It is a modular framework rather than one fixed algorithm: each stage can use different objectives and heuristics. Graphviz's dot, for example, implements this style of layout and aims to keep directed edges pointing the same way while reducing crossings and edge length.2

The Pipeline

A practical implementation has five stages:

  1. Remove cycles by temporarily reversing or otherwise marking selected edges.
  2. Assign every vertex to a discrete layer, also called a rank.
  3. Order the vertices within each layer to reduce edge crossings.
  4. Assign coordinates while preserving those layers and orders.
  5. Restore and route the original edges through the resulting geometry.3

Each stage commits information that constrains the next one. A compact rank assignment can make crossing reduction harder. A locally good vertex order can prevent straight edges during coordinate assignment. Saving the best complete drawing is therefore more useful than accepting every locally improved intermediate result.

Cycle Removal

Layer assignment needs a directed acyclic graph (DAG): for each edge u -> v, v must be placed later than u. A cyclic input cannot satisfy that condition.

One common solution finds a feedback arc set, a set of edges whose removal makes the graph acyclic, and reverses those edges during layout. Finding the smallest such set is expensive, so implementations use greedy or depth-first-search heuristics. The final drawing restores the original directions, which means a few edges may point against the dominant flow. Prefer reversing low-weight or explicitly reversible edges when the graph gives some relationships higher semantic priority.

Collapsing each strongly connected component into one compound vertex is another option. It preserves a cycle as a meaningful group instead of presenting one of its edges as an exception. The component's internal graph can be laid out separately.

Layer Assignment

For a DAG, layer assignment chooses an integer rank r(v) for every vertex. An edge with a minimum span d(u, v) imposes the constraint

r(v) >= r(u) + d(u, v)

A longest-path assignment is simple and fast. A network-simplex assignment can instead minimize the weighted sum of edge spans under these constraints, usually producing fewer layers or less total edge length. User constraints such as “same rank,” a minimum edge length, or an edge that should not affect ranking belong in this stage. Graphviz exposes all three ideas through rank, minlen, and constraint.2

An edge that skips layers is then replaced internally by a chain of segments with a dummy vertex in every intermediate layer:

A (rank 0) -> B (rank 3)

A -> d1 -> d2 -> B
0     1     2     3

This produces a proper layering, where every segment joins adjacent layers. Dummy vertices participate in ordering and coordinate assignment, but later become bends or control points on the original edge. A ranker should avoid unnecessary long edges because they increase both the number of dummy vertices and the work in later stages.

Crossing Reduction

Once the ranks are fixed, crossings depend on the left-to-right order of vertices within each rank. Even one-sided crossing minimization—reordering one layer while its neighbor is fixed—is NP-hard, so layered layout engines generally use repeated sweeps and heuristics.3

During a downward sweep, keep one layer fixed and sort each vertex in the next layer by the positions of its neighbors in the fixed layer. Two common keys are:

  • the barycenter, or arithmetic mean of neighbor positions
  • the median neighbor position, which is less affected by one distant neighbor

Then sweep upward using outgoing neighbors as the reference. Alternate directions, transpose adjacent vertices when a swap removes crossings, and retain the best ordering seen. Stable tie-breaking matters: equal keys should preserve the previous order or use a stable vertex ID, otherwise the layout can change between identical runs.

Crossings between two adjacent layers can be counted as inversions. List the lower endpoints in the order induced by edges whose upper endpoints are scanned left to right. Every inverted pair corresponds to a crossing. A Fenwick tree or merge-sort counter avoids checking every pair when layers are dense.

Dummy vertices need care here. Keeping the dummy chain for one long edge aligned where possible reduces bends and prevents long edges from weaving unnecessarily through the drawing. Ports, fixed sibling orders, clusters, and user-pinned vertices add ordering constraints that a plain barycenter sort must respect.

Coordinate Assignment and Routing

The order now fixes which vertex is left of which, but not the distance between them. Coordinate assignment chooses positions subject to non-overlap constraints based on each node's actual width. It also tries to align vertices and dummy chains vertically, compact the drawing, and avoid needless bends.

The Brandes–Köpf algorithm does this in linear time for a fixed layered ordering. It forms vertical alignments with median neighbors, resolves alignment conflicts, and horizontally compacts the resulting blocks. Running the construction in the four combinations of up/down and left/right bias, then balancing those results, avoids consistently favoring one side of the graph.4

Only after node boxes have coordinates should the renderer choose exact edge endpoints, arrow routes around nodes, place arrowheads and labels, and turn dummy chains into polylines or splines. Separating layout from routing also lets the renderer account for ports and nonuniform shapes. Reversed edges from cycle removal keep their original arrow direction even if their route travels against the main flow.

Practical Choices

The pipeline exposes several competing measures: crossings, total edge length, bends, drawing width, drawing height, symmetry, and stability between edits. There is no ordering that optimizes all of them. Choose priorities from the diagram's purpose rather than hiding them in a single unexplained score.

For a small implementation, a useful baseline is:

greedy cycle removal
longest-path ranking
one dummy vertex per skipped layer
alternating median sweeps with adjacent transpositions
simple left-to-right compaction using node widths
polyline routing through dummy vertices

Keep original vertices and edges separate from temporary layout objects. Record reversed edges, map every dummy chain back to its original edge, and make all ties deterministic. This makes it possible to replace one stage later with network simplex, Brandes–Köpf coordinates, constrained ordering, or spline routing without rewriting the whole layout engine.

References

  1. K. Sugiyama, S. Tagawa, and M. Toda, “Methods for Visual Understanding of Hierarchical System Structures”, 1981. ↩

  2. Graphviz, dot layout documentation and E. R. Gansner et al., “Graphviz and Dynagraph — Static and Dynamic Graph Drawing Tools”. ↩ ↩2

  3. Till Tantau and Jannis Pohlmann, “Graph Drawing Algorithms: Layered Layouts”, PGF/TikZ Manual. ↩ ↩2

  4. Ulrik Brandes and Boris Köpf, “Fast and Simple Horizontal Coordinate Assignment”, 2002. ↩