Mastering Hierarchical Graph Layout: A Deep Dive into Sugiyama’s Algorithm

Introduction

Graphs are a common data structure used to represent relational data, and visualizing them often requires automatic layout. For hierarchical relationships, a layered layout—typically applied to Directed Acyclic Graphs (DAGs)—is used.

Hierarchical Layout of Graphs

When data has a clear hierarchy or ordering, a layered layout is appropriate. Common scenarios include flowcharts, organization charts, and state transition diagrams.

The hierarchical layout method, first detailed by Kozo Sugiyama in 1981, is often called the Sugiyama layout.

Purpose

The goal is to automatically produce an easy‑to‑understand hierarchical drawing of a graph.

Hierarchical node placement

Minimize edge crossings

Straight edge paths

Short edge paths

Balanced layout

Basic Drawing Rules

Place all nodes of a layer on the same horizontal line without overlap.

Draw each edge as a straight line.

After layering nodes, placing each layer’s nodes at reasonable horizontal positions yields the final drawing.

Layout Idea

Sugiyama splits the layout problem into four steps, each solving a sub‑problem.

Step 1: Node Layering

Assign nodes to layers based on edge direction.

If an edge spans multiple layers, insert dummy nodes on each intermediate layer so that every edge connects adjacent layers.

Step 2: Reduce Crossings

With nodes layered, the crossing reduction problem becomes ordering nodes within each layer. This problem is NP‑hard, so heuristic methods such as the Barycenter (centroid) and Median algorithms are commonly used.

Step 3: Compute Coordinates

The aim is to make edges as vertical as possible, keep the layout balanced, and shorten long edges. Sugiyama proposed a quadratic‑programming approach and a priority‑based heuristic; many later works provide faster heuristics. One practical heuristic (used in dagre) aligns nodes with the median of their adjacent nodes, then performs vertical alignment, horizontal compression, and conflict resolution in four directions (left‑up, left‑down, right‑up, right‑down) before balancing the results.

Step 4: Draw

Place nodes at the computed positions, remove dummy nodes and edges, and render the final graph.

Algorithms for Each Step

Node Layering

Common algorithms include:

Longest Path: fast but may place nodes too low, leaving large empty space.

Tight Tree (Network Simplex): optimizes layer assignment to reduce total edge length and the number of dummy nodes.

Crossing Reduction

Heuristics such as Barycenter and Median reorder nodes within each layer to minimize edge crossings.

Coordinate Assignment

A fast heuristic used in dagre aligns nodes with the median of their neighbors, then performs vertical alignment, conflict resolution, and horizontal compression.

Additional Considerations

Incremental layout: preserve existing layout when adding nodes/edges.

Nested graphs: handle sub‑graphs within nodes.

Edge labels: account for label size when positioning.

Edge styles: straight, orthogonal, or curved edges may require different algorithms.

Node ports: edges may need to attach to specific ports on a node.

Implementing Your Own Layout

Because Sugiyama’s framework separates the problem into modular steps, you can replace any step with a custom algorithm to suit specific requirements, such as centering nodes for simple flowcharts.

Simple JavaScript Implementation – dagre

dagre is a JavaScript library that implements hierarchical layout and is used by G6.

function runLayout(g, time) {
  // makeSpaceForEdgeLabels
  time("makeSpaceForEdgeLabels", function() { makeSpaceForEdgeLabels(g); });
  // removeSelfEdges
  time("removeSelfEdges", function() { removeSelfEdges(g); });
  // acyclic conversion
  time("acyclic", function() { acyclic.run(g); });
  // nesting graph layout
  time("nestingGraph.run", function() { nestingGraph.run(g); });
  // Step 1. rank (layering)
  time("rank", function() { rank(util.asNonCompoundGraph(g)); });
  // inject edge label proxies
  time("injectEdgeLabelProxies", function() { injectEdgeLabelProxies(g); });
  // remove empty ranks
  time("removeEmptyRanks", function() { removeEmptyRanks(g); });
  // cleanup nesting graph
  time("nestingGraph.cleanup", function() { nestingGraph.cleanup(g); });
  // normalize ranks
  time("normalizeRanks", function() { normalizeRanks(g); });
  // assign rank min/max
  time("assignRankMinMax", function() { assignRankMinMax(g); });
  // remove edge label proxies
  time("removeEdgeLabelProxies", function() { removeEdgeLabelProxies(g); });
  // normalize long edges
  time("normalize.run", function() { normalize.run(g); });
  time("parentDummyChains", function() { parentDummyChains(g); });
  time("addBorderSegments", function() { addBorderSegments(g); });
  // Step 2. order (node sorting)
  time("order", function() { order(g); });
  // re‑insert self‑edges
  time("insertSelfEdges", function() { insertSelfEdges(g); });
  // adjust coordinate system (horizontal/vertical)
  time("adjustCoordinateSystem", function() { coordinateSystem.adjust(g); });
  // Step 3. position (node placement)
  time("position", function() { position(g); });
  time("positionSelfEdges", function() { positionSelfEdges(g); });
  time("removeBorderNodes", function() { removeBorderNodes(g); });
  // undo normalization of long edges
  time("normalize.undo", function() { normalize.undo(g); });
  time("fixupEdgeLabelCoords", function() { fixupEdgeLabelCoords(g); });
  time("undoCoordinateSystem", function() { coordinateSystem.undo(g); });
  time("translateGraph", function() { translateGraph(g); });
  // assign node intersections
  time("assignNodeIntersects", function() { assignNodeIntersects(g); });
  // reverse edges that were reversed during acyclic conversion
  time("reversePoints", function() { reversePointsForReversedEdges(g); });
  time("acyclic.undo", function() { acyclic.undo(g); });
}

Summary

The article introduces the concepts, steps, and algorithms of hierarchical graph layout.

The process consists of node layering, crossing reduction, coordinate computation, and drawing (or an additional acyclic conversion step).

Each step is a complex sub‑problem with many heuristic solutions, and custom algorithms can be applied to meet specific business needs.

References

Github – dagre/dagre

Github – d3‑dag

G6

Eclipse Layout Kernel

Wiki – Layered Graph Drawing

图可视化之图布局

深入解读Dagre布局算法

Methods for Visual Understanding of Hierarchical System Structures

A Technique for Drawing Directed Graphs

Fast and Simple Horizontal Coordinate Assignment

Layout of Compound Directed Graphs

An Efficient Implementation of Sugiyama’s Algorithm for Layered Graph Drawing

Port Constraints in Hierarchical Layout of Data Flow Diagrams

Improved Vertical Segment Routing for Sugiyama Layouts