Visualization of Graphs - Lecture 8 - Hierarchical Layouts: Sugiyama Framework - Hierarchical Drawing - Motivation

Oct 23, 2026

Lecture 8 explains hierarchical graph drawing with the Sugiyama framework. It defines the problem as producing a drawing of a directed graph that closely reproduces hierarchical properties while meeting desirable constraints such as upward-directed edges, placement of vertices on few horizontal layers, limited edge crossings, short edges, and even spacing—noting that criteria can be contradictory. The lecture then introduces step 1, cycle breaking, formulated as a minimum feedback arc set (NP-hard) and a greedy heuristic for constructing an acyclic digraph, followed by the intuition behind assigning vertex y-coordinates and orienting edges upward.

LanguageEnglish

CategoryTechnology

FormatPDF

Pages49

Reading Time2 h 3 min

AccessFree to download

Lecture 8: Hierarchical Layouts: Sugiyama Framework

Hierarchical Drawings – Motivation

Hierarchical Drawing: Problem Statement and Desirable Properties

Hierarchical Drawing – Applications

Classical Approach: Sugiyama Framework

Step 1: Cycle Breaking

Heuristic GreedyMakeAcyclic

Vertex Placement and Upward Edge Orientation

Visualization of Graphs Lecture 8: Hierarchical Layouts: Sugiyama Framework | | | | | --- | --- | --- | |

7 | | | |
6

| | | |
|
3 2 1
| | | | | | 4 Alexander Wolff Summer term 2025 2-2 Hierarchical Drawings – Motivation 3-8 Hierarchical Drawing Problem Statement: ■ Input: digraph G ■ Output: drawing of G that “closely”reproduces the hierarchical properties of G Desirable Properties: ■ edges are directed upwards, ■ vertices lie on (few) horizontal lines,■ few pairs of edges cross, ■ edges are short, ■ vertices are evenly spaced. Criteria can be contradictory! 4-1 Hierarchical Drawing – Applications yEd Gallery: Java profiler JProfiler using yFiles 4-3 Hierarchical Drawing – Applications Source: Randall Munroe, [https://xkcd.com/657](https://xkcd.com/657) Source: Tanahashi & Ma,”Design Considerations for Optimizing Storyline Visualizations”, TVCG 2012 Hierarchical Drawing – Applications Source: Visualization that won the Graph Drawing Contest, Creative Track, 2016 . Klawitter & Mchedlidze 5-7 Classical Approach: Sugiyama Framework [Sugiyama, Tagawa, Toda ’81] 6-1 Step 1: Cycle Breaking 6-10 Step 1: Cycle Breaking Approach. ■ Find minimum-size set E ⋆ of edges that are not upward. ■ Remove E ⋆ and insert reversed edges. Problem Minimum Feedback Arc Set (FAS) . ■ Input: directed graph G ■ Output: minimum-size set E ⋆ ⊆ E (G) such that. . . NP-hard edges in E ⋆ but reversed G⋆ = (V(G), E (G) \ E⋆ ) acyclic (E(G) \ E⋆ ) ∪ E ⋆rev 7-21 Heuristic 1 GreedyMakeAcyclic(Digraph G): E′ ← ∅ foreach v ∈ V (G) do if |E→ (v)| ≥ |E← (v)| then E′ ← E′ ∪ E→ (v) else E′ ← E′ ∪ E← (v) remove v and E (v) from G. return G′ = (V(G), E′) ■ G′ is a DAG. [Berger, Shor ’90] v E → (v) := { (v, u): (v, u) ∈ E (G)} E ← (v) := { (u, v): (u, v) ∈ E (G)} E (v) := E → (v) ∪ E← (v) Proof Idea. Place the vertices on distinct y-coordinates. y-coordinates increase/decrease towards the middle. All edges point upwards.

FAQs

What is the hierarchical drawing problem in this lecture?

Given a directed graph G, the goal is to output a drawing that closely reproduces the hierarchical properties of G. The drawing emphasizes upward edges, layered vertex placement, few crossings, short edges, and even vertex spacing.

Which desirable properties does the lecture list for hierarchical drawings?

Edges should be directed upwards; vertices should lie on few horizontal lines; few edge pairs should cross; edges should be short; and vertices should be evenly spaced.

Why is cycle breaking step 1 important, and how is it handled?

Cycle breaking ensures the graph becomes acyclic by reversing a chosen set of edges. The lecture frames this as the minimum feedback arc set problem, notes it is NP-hard, and presents a greedy heuristic GreedyMakeAcyclic to construct a DAG.

Oct 23, 2026

Upload by วิน