Overview
The Sugiyama framework turns a directed graph into a layered drawing through staged steps: break cycles if needed, assign ranks, order vertices within each layer to reduce crossings, and place coordinates.
CoreSource checked
Sugiyama Layered Drawing
Draws directed graphs in layers by ranking vertices, reducing crossings, and assigning coordinates.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Intermediate
- Family
- Graph Drawing
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
Core Concepts
layered graph drawinggraph drawinggraph traversal
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O((V + E) log V)
Worst
O(V^2 + E)
Space
O(V + E)
When to Use
- Use when direction and hierarchy should be visually emphasized.
- Use when a staged layout pipeline is acceptable and crossing reduction can be heuristic.
When Not to Use
- Avoid when the graph has no meaningful direction or hierarchy.
- Avoid when exact crossing minimization is required for large graphs.
What It Does
- Assigns vertices to ordered layers
- Reduces edge crossings between neighboring layers
- Places vertices and routes edges for a readable layered drawing
Use Cases
- Flowchart and dependency graph layout
- DAG-style visualization
- Readable drawings of directed process graphs
Inputs
- Graph G = (V, E) or rooted tree T
- Viewport bounds and spacing parameters
Outputs
- 2D vertex coordinate map (x_v, y_v) minimizing crossings or force energy
Pseudocode
- 1.If needed, reverse or mark edges to break cycles
- 2.Assign each vertex to a rank or layer
- 3.Insert dummy vertices for long edges
- 4.Order vertices within layers to reduce crossings
- 5.Assign coordinates and route edges
- 6.Return the layered drawing
Canonical Example
- Input
- edges A->B, A->C, B->D, C->D
- Output
- A in the top layer, B and C in the middle, D in the bottom layer
- Explanation
- Ranking follows edge direction, then B and C can be ordered to reduce crossings.
Implementation Notes
- Keep cycle removal, ranking, crossing reduction, and coordinate assignment as separate stages.
- Record tie-breaking for deterministic layout tests.
- Test on a tiny DAG and a graph with one back edge.
Common Pitfalls
- Cycles must be handled before rank assignment in many pipelines.
- Crossing reduction is usually heuristic, so output can depend on tie-breaking.
- Long edges may need dummy vertices to route through layers cleanly.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow assigning ranks, reducing crossings, and placing vertices in layers on a small layered graph drawing example.
Step 1 of 6: If needed, reverse or mark edges to break cycles
graph-traversal-mechanismNotes
Sugiyama layout is a framework of heuristics; deterministic tie-breaking matters for reproducible diagrams.
Sources (2)
What each reference supports for this entry.
Handbook of Graph Drawing and Visualization
BookGraph drawing reference for Sugiyama Layered Drawing's layout objective, drawing constraints, and visual graph model.
Open sourceEfficient Sugiyama Implementation
PaperReference for layered graph drawing and efficient dummy-vertex handling in Sugiyama-style layouts.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toFruchterman-Reingold Layout
Graph Traversal · Core
Sugiyama emphasizes direction and layers, while force-directed layout emphasizes spatial balance.
Compare with thisRelationships
View full relationship pageAlternative toFruchterman-Reingold Layout
Sugiyama emphasizes direction and layers, while force-directed layout emphasizes spatial balance.
Conceptual neighborReingold-Tilford Tree Layout
Both produce structured graph drawings, but tidy tree layout assumes a tree.
Conceptual neighborWalker Tree Layout
Both place hierarchical structures, but Sugiyama handles more general directed graphs.
Tags
GraphTraversal