TU Wien:Graph Drawing Algorithms VU (Nöllenburg)/Zusammenfassung 2024S

Introduction

This is a summary of the Graph Drawing Algorithms lecture by Nöllenburger. It covers all topics presented in the lecture and tries to explain concepts in somewhat "plain" English that were only shown with drawings or math on the slides. In general my colleague and I tried to translate some of the unnecessarily complex language to a version that lends itself better to memorization. We also skipped some things (eg. a few proofs) we did not feel like memorizing, or did not fully understand. You should definitely read the slides (all 1000 of them) at least once, take a good look at the figures and drawings. In some places we reference to them.

Visual Variables

• Size
• Shape
• Orientation
• Color
• Texture
• Value (Opacity)
• Postion → Layout Problem!

Quality Criteria

• Drawing Conventions → required (straight line, orthogonal, grid, crossing free, ...)
• Aesthetics → optimize (#crossings, #bends, edge length, area, ...)
• Local constraints (relative positions, groups of vertices)

Often NP-hard optimization problems & competing criteria.

Tree Layout

Binary Tree

Conventions & Criteria

Drawing conventions

• straight edges & no crossings
• hierarchical
• layers
• symmetric child placement
• isomorphic subtrees (subtrees with same configuration are drawn the same)

Quality criteria

• dimensions (height, width, area)
• balanced subtree placement

Simple: Tree Traversal

Pre-order (P,L,R); In-order (L,P,R); Post-order (L,R,P)

DFS

• Post-order traversal: index(v) → x, depth(v) → y
• running time: O(n)
• drawing area: n * depth(T)
• Edges not uniform & parent/root not centered

Reingold/Tilford (2-Phase-Algorithm)

• Improve the area and center the parent
• Divide & Conquer
  • 1. Draw sub trees recursively
  • 2. Place subtree drawings with distance 2 or 3 next to each other. Find minimal distance with tighter contour!

Phase 1

1. Compute the contour & x-offsets to parents of both subtrees
2. Compute distance per level ${\textstyle |dr-dl|+2}$
3. Pick maximum distance ${\textstyle d_{v}}$ → round up ${\textstyle d_{v}/2}$ as distance left & right of root
4. Merge contours

Running time: O(n) → Each node compared at most twice (once on left, once on right contour → 2n) Contour stored as linked list with x-offsets for each vertex

Phase 2

1. Traverse in Pre-order
2. Compute absolute x positions → accumulate offsets of all parents per vertex

Running time: ${\textstyle O(n)}$
Area: ${\textstyle O(n\cdot depth(T))}$

Worst case for area is a string of nodes as a line → height = n → n*n area

Theorem: Ordered rooted binary tree → straight line drawing in O(n) time and O(n²) area

Satisfies: parent-child-order, isomorphic subtrees, integer grid

Width can be minimized further, when subtrees are not drawn isomorphicly (dependencies between subtrees) → NP-hard problem

2-Phase-Algorithm can be extended for non-binary trees with still O(n) time

Radial Tree Layout

Concentric rings instead of layers; often for unrooted trees

Conventions & Criteria

• straight edges & no crossings
• concentric rings
• balanced distribution

Planarity

• Put each subtree into its own wedge on the ring
• Distribute the wedges according to size of subtree ${\textstyle T(u)}$
• Limit space of children to tangent of parent vertex to prevent edges from crossing over parent rings

Tangent-restricted wedge angle for subtree T(u): ${\textstyle \tau _{u}}$

${\textstyle \tau _{u}=}$ min{proportion by size(wedge), max tangent angle} ${\textstyle =\min\{{\frac {|T(u)|}{|T(p(u))|-1}}\cdot \tau _{p(u)},2\cdot arccos({\frac {\rho _{i}}{\rho _{i+1}}})\}}$

Algorithm

1. Compute subtree sizes ${\textstyle |T(u)|}$ by traversing in post-order (count vertices bottom to up)
2. Compute angles recursively in pre-order

Theorem: Rooted tree → planar radial drawing in O(n) time

HV-Layout

Compact Orthogonal Tree Drawing: planar, straight line drawing of rooted unordered binary tree

Subtree bounding boxes are placed either on top of, or next to each other → Can be swapped: 4 possible options, but ordering lost

Right Heavy HV Tree: Place heavier subtree to the right next to the sibling (horizontal combination) → bottom up construction

Height is ${\textstyle log(n)}$ because we stack the subtrees
Worst case width (single string of nodes) is n → ${\textstyle width\leq n}$

Theorem: Rooted binary tree → HV drawing in O(n) time and O(n * log(n)) area

Area can be optimized with dynamic programming in O(n²) time

Series Parallel Graphs

Has a source s and sink t, and is composed by connecting two SP graphs in series or in parallel

• Series Composition: ${\textstyle s_{1}}$, ${\textstyle t_{1}=s_{2}}$, ${\textstyle t_{2}}$
• Parallel Composition: ${\textstyle s_{1}=s_{2}}$, ${\textstyle t_{1}=t_{2}}$

Decomposition Tree

• Q-Node: Single edge
• P-Node: Parallel composition of two sub graphs
• S-Node: Series composition of two sub graphs

Lemma: SP graphs are planar & acyclic

Proof by induction:

• Base case: Q-Node is single edge → planar & acyclic. Source is lower than sink → all edges point upwards
• Induction S-Composition:
  • Planarity: all edges point upwards, when stacked on t1=s2 no edges can cross
  • Acyclic: A newly created cycle through t1=s2 passes vertex twice, thus would need pre-existing cycles in the subgraphs
• Induction P-Composition:
  • Planarity: Subgraphs can be placed next to each other, and edges can be extended to reach s=s1=s2 and t=t1=t2 without crossings
  • Acyclic: s=s1=s2 remains as a source and t=t1=t2 remains as a sink → no new cycles

Properties

• Graph can be tested for SP in O(n) time, and decomposition tree can be constructed in O(n) time
• Many NP-hard problems are O(n) on SP graphs (eg. max independent set, ...)
• SP graphs used for flow charts, electrical circuit diagrams, ...

Drawing

Conventions & Criteria

• straight edges & no crossings
• upward edges
• optimize area

Exponential Lower Bound for Area

Theorem: There is a family of SP graphs that require exponential size with straight edges when preserving the ordering. ${\textstyle \Omega (4^{n})}$

• Any SP graph is combined with series and parallel combination twice
• The new contour is a triangle of the vertices ${\textstyle s_{n+1}}$, ${\textstyle s_{n}}$, and ${\textstyle t_{n+1}}$
• It can be shown when wrapping again, to fit the triangles so that edges do not cross, 4 times the space is necessary
• The area increases exponentially with ${\textstyle 4^{n}}$
• See further details in figure on VL03/38

Polynomial Drawing Area

Divide & conquer algorithm based on decomposition tree

• Draw subgraph in isosceles (cathetes of same length), right-angled triangle
• left (right-angle) vertex always empty
• s & t in lower & upper corner
• parallelogram in corners of s & t to neighboring vertices → always empty

Structure/Composition

• Q node only has single edge from s to t (hypotenuse)
• S node stacks the triangles
• P node puts the triangles next to each other
  • Q nodes always have to be pushed to the right (else s and t cannot be connected)
  • P node of two Q nodes not allowed on simple (not multi) graph!
  • right push changes ordering!
  • The tip of the right triangle can be positioned on the hypotenuse of the left one between the left one's parallelograms, even if the space has zero length (because the tip has no vertex, no vertex is put into the parallelograms) (parallelograms may also not/cannot overlap)

Polynomial Area

Theorem: Simple SP graph with m edges → right-pushed drawing (upward planar) in O(m²) area

Proof by induction: (see VL03/54)

• Base case:
  • Q-Node is single edge (m=1) with length l → ${\textstyle A={\frac {l^{2}}{4}}}$
  • on an integer grid l=2 → ${\textstyle l=2\cdot m}$
  • ${\textstyle A={\frac {1}{2}}\cdot 1\cdot 2=1=m^{2}}$
• Induction S-Composition:
  • Lengths of the hypotenuses add up → each hypotenuse is bounded by ${\textstyle l=2\cdot m}$ → ${\textstyle 2\cdot m_{1}+2\cdot m_{2}=2\cdot m}$
  • Area computation is unchanged → ${\textstyle A={\frac {1}{2}}\cdot m\cdot 2m=m^{2}}$ → still m²
• Induction P-Composition:
  • By putting triangles next to each other, the sides of the left one are extended to form a larger new one. The lengths of the hypotenuses are again being added up.
  • Same as above.

Arbitrary Graphs

Conventions & Criteria

• straight edges & few crossings
• no node overlaps
• group densely connected subgraphs
• bounded edge lengths
• small area

Force Based Model

Spring Embedder

Physical model where...

• edges are simulated springs
• vertices are connected by springs and are simulated particles with forces acting on them (e.g. springs, electrical, magnetic, gravitational)

Definition

Repulsive force (not-connected vertices): Same as electrically charged particles set by a constant ${\textstyle c_{rep}}$ and tapers off with distance²

${\textstyle f_{rep}(p_{u},p_{v})={\frac {c_{rep}}{distance^{2}}}\cdot direction={\frac {c_{rep}}{||p_{u}-p_{v}||^{2}}}\cdot {\overrightarrow {p_{u}p_{v}}}}$

Attractive force (connected vertices): Spring constant scaled by the logarithmic stretch (when compressed the stretch is <1 and the direction inverted due to the log)
${\textstyle f_{spring}(p_{u},p_{v})=c_{spring}\cdot \log {stretch}\cdot direction=c_{spring}\cdot \log {\frac {||p_{u}-p_{v}||}{l}}\cdot {\overrightarrow {p_{v}p_{u}}}}$

For each vertex: sum all forces (fspring when connnected and frep when not)

Algorithm

1. While not max iterations & at least one force ${\textstyle >\epsilon }$
   1. Compute summed force ${\textstyle F_{v}(t)}$ for each vertex v
   2. For each vertex: Apply the force with damping factor to the position ${\textstyle p_{v}=p_{v}+\delta (t)\cdot F_{v}(t)}$

Run time: The force computation takes O(n²) time per iteration (all vertices interact with each other), with K iterations → O(K * n²)

Advantages & Disadvantages

• (+) simple
• (+) good results for small/medium graphs
• (+) empirically good representation of symmetries & structure
• (-) system not stable at end
• (-) local minima
• (-) computing time (frep in O(|V|²) )
• (-) initial placement has strong influence

Fruchterman & Reingold

Only use particle analogy with attractive and repulsive forces instead of springs. On close distances the repulsive forces overtake the attractive forces similar to compressed springs.

Repulsive force between all vertices:
${\textstyle f_{rep}(p_{u},p_{v})={\frac {optimaldistance^{2}}{distance}}\cdot direction={\frac {l^{2}}{||p_{u}-p_{v}||}}\cdot {\overrightarrow {p_{u}p_{v}}}}$

Attractive force only between connected vertices:
${\textstyle f_{attr}(p_{u},p_{v})={\frac {distance^{2}}{optimaldistance}}\cdot direction={\frac {||p_{u}-p_{v}||^{2}}{l}}\cdot {\overrightarrow {p_{v}p_{u}}}}$

When the distance is optimal the forces cancel out, when the distance is smaller than optimal, the repulsive force takes over.

${\textstyle ||p_{v}-p_{u}||=l}$ → ${\textstyle {\frac {l^{2}}{||p_{u}-p_{v}||}}\cdot {\overrightarrow {p_{u}p_{v}}}+{\frac {||p_{u}-p_{v}||^{2}}{l}}\cdot {\overrightarrow {p_{v}p_{u}}}={\frac {l^{2}}{l}}\cdot {\overrightarrow {p_{u}p_{v}}}+{\frac {l^{2}}{l}}\cdot {\overrightarrow {p_{v}p_{u}}}=l-l=0}$

Modifications

• Inertia: force gets scaled by mass (degree of vertex)
• Gravitation: gravitational pull to a barycenter of vertices based on own mass (degree)
• Magnetic: Additional force applied to straighten out edges horizontally or vertically

Adaptive displacement

Change the damping factor for each vertex based on last iteration. Higher temperature means less damping.

When force points in...

• same direction → increase temperature: Let vertex move towards final position quicker
• opposite direction → reduce temperature: Prevent oscillation (moving back and forth)
• orthogonal direction (frequently) → reduce temperature: Prevent rotation around a center point

Advantages & Disadvantages

• (+) still simple
• (+) better layout and faster convergence
• (-) ... same as Spring Embedder

Local Repulsive Force Computation

Repulsive force computation needs quadratic time in respect to the number of vertices → make it faster

Grid

• Subdivide plane into grid of cell-size ${\textstyle d_{max}}$
• Only check the neighboring grid cells
• Only use vertices within distance ${\textstyle d_{max}}$

Useful, but quality loss (no long-range forces), and risk of oscillation around ${\textstyle d_{max}}$

Worst-case no improvement

Quad Tree

• Subdivide the plane into a recursive quad tree (each cell contains max one vertex)
• Compute center of mass and node count for each cell in tree (bottom up)
• For each vertex u:
  • Traverse root to u (Top down)
  • For all siblings ${\textstyle v_{i}}$ on current level check ${\textstyle {\frac {cellwidth}{distance\_mass\_center}}<\theta }$
  • When below approximate with the precomputed center of mass
  • Else recurse down the tree

With balanced point distribution → quad tree balanced → traversal time O(n * log(n))

Stress Based Model

Multidimensional Scaling (MDS)

Compute some ideal distances between each vertex pair and come up with a layout that minimizes deviations from these distances. For ideal distances use the shortest path between the vertex pair through the graph ${\textstyle d_{ij}}$.

Stress between two points i and j: ${\textstyle s_{ij}=weight\cdot (actual\_dist-ideal\_dist)^{2}=w_{ij}\cdot (||p_{i}-p_{j}||-d_{ij})^{2}}$

The weight is e.g.: ${\textstyle w_{ij}={\frac {1}{d_{ij}^{2}}}}$ → Ideally far away vertices do matter very little

The overall stress is the sum of each unique pair's stress. → ${\textstyle s(p)=\sum _{i<j}s_{ij}}$

Stress Minimization

1. Compute all pairwise distances (eg. All Pairs Shortest Path)
2. minimize stress s(p) (e.g. Stress Majorization)

Scalability

Too slow for large graphs due to super-quadratic run times. Faster approximations:

• PivotMDS
• MaxEnt Stress
• Sparse Stress

Comparison

Force based

• simple
• any input graph
• good layouts for small & sparse graphs
• flexible
• robust & scalable

Stress based

• higher quality (?)
• any input graphs
• optimization with iterative solving of equations or gradient descent

But

• no guaranteed convergence
• dependence on input layout
• stress based needs approximations for large graphs

Straight-Line Planar Graphs

Planar Graphs

Definition: Planar graph → Graph drawable in 2D without crossings

Definition: Plane graph → Planar graph + embedding

Two planar drawings have the same embedding if they have the same rotation scheme and the same external face.

Theorem: Graph is planar iff there is no ${\textstyle K_{5}}$ or ${\textstyle K_{3,3}}$ minor

Theorem: Simple graph → Testing planarity & creating embedding has O(n) time

Theorem: Planar graph → straight line drawing

Theorem: Planar graph → disk contact representation

Theorem: Connected planar graph → ${\textstyle |V|-|E|+|F|=2}$

Theorem: 3 connected planar graph → straight-line convex drawing in O(n) time.

Theorem: Embedded planar graph → straight line drawing on ${\textstyle (2n-4)\cdot (n-2)}$ grid.

Triangulation

Many algorithms use maximally planar graphs → triangulated graphs.

1. Add all missing edges to triangulate graph (including the outer face!)
2. Do the algorithm on the maximally planar/triangulated graph
3. Remove the unnecessary edges

Canonical Ordering

As an idea for an drawing algorithm for planar graphs, we could draw the graph incrementally by adding each vertex and connecting it to the rest of the drawing. For this we need an ordering.

Definition: Triangulated planar embedded graph → ordering of vertices is canonical iff

• ${\textstyle \{v_{1},...,v_{k}\}}$ for the first k vertices induces 2-connected internally triangulated graph ${\textstyle G_{k}}$
• first edge ${\textstyle (v_{1},v_{2})}$ always on outer face of graph (boundary)
• On ${\textstyle G_{k}}$ the next vertex to connect ${\textstyle v_{k+1}}$ is outside of ${\textstyle G_{k}}$, and it connects to vertices on the boundary ${\textstyle C_{k}}$ that all lie next to each other (no skipping)

Lemma: Triangulated planar graph → canonical ordering

Proof using inverse induction:

• Hypothesis: ${\textstyle \{v_{k+1},...,v_{n}\}}$ such that all three conditions are met on ${\textstyle G_{k}}$
  • For the next vertex ${\textstyle v_{k}}$ it is sufficient that it is not part of a chord (see VL05/38)
• Inverse induction step: If we can now select ${\textstyle v_{k}}$ that is not part of a chord with ${\textstyle G_{k}}$ being 2-connected → ${\textstyle G_{k-1}}$ also has to be 2-connected → ${\textstyle G_{k-1}}$ meets the three conditions
  • Assume ${\textstyle G_{k-1}}$ not 2-connected (see VL05/56)
    • Either ${\textstyle G_{k}}$ would not be 2-connected → contradiction
    • Or ${\textstyle G_{k}}$ would not be triangulated → contradiction
    • Or ${\textstyle v_{k}}$ would be part of chord → contradiction
  • Further we can always find a chord free vertex
    • Chords form a nesting
    • There is always a inner most chord with at least one vertex nested inside (simple graph)
• The ordering is canonical

Lemma: Canonical ordering can be created in O(n) time.

Shift Algorithm

Draw a planar graph with a canonical ordering on a grid. Invariants:

• ${\textstyle v_{1}}$ is on ${\textstyle (0,0)}$ and ${\textstyle v_{2}}$ is on ${\textstyle (2k-4,0)}$ → width of the drawing ${\textstyle 2n-4}$
• Boundary is drawn x-monotone (strictly left to right) (except bottom edge)
• All slopes on boundary are 45° (+/-1 )

Algorithm

1. Base line for ${\textstyle v_{1}}$ and ${\textstyle v_{2}}$
2. For each vertex ${\textstyle v_{k}}$ in canonical ordering
   1. Shift the vertices between first and last +1 to the right (with subtree)
   2. Shift everything beyond and including the last +2 to the right (with subtree)
   3. Place ${\textstyle v_{k}}$ on the intersection of extended slopes from it's first and last neighbor
   4. Connect it

• We shift ${\textstyle v_{2}}$ +2 for every vertex except ${\textstyle v_{1}}$ and ${\textstyle v_{2}}$ → width ${\textstyle 2n-4}$
• The last vertex ${\textstyle v_{n}}$ is x-centered → x coordinate ${\textstyle n-2}$ → with slopes 45° → height ${\textstyle n-2}$
• Area: ${\textstyle (2n-4)(n-2)}$ → O(n²)

Planarity Proof

Lemma: On a planar straight-line grid drawing ${\textstyle G_{k}}$ each vertex ${\textstyle w_{i}}$ on the boundary (except ${\textstyle v_{1}}$, ${\textstyle v_{2}}$) is the root of a tree ${\textstyle L(w_{i})}$ of covered internal vertices. Each tree is x-shifted by ${\textstyle \delta _{i}}$ to the right with ${\textstyle 0\leq \delta _{1}\leq ...\leq \delta _{t}}$. The resulting grid drawing is still planar and straight-line.

Aka: we can shift all trees without letting them switch places (left ones are never shifted more than right ones) the drawing is still intact.

Proof by induction

• Base case: ${\textstyle G_{3}}$ holds
• Induction: When the lemma holds for ${\textstyle G_{k-1}}$ and we can shift its subtrees such that it holds for ${\textstyle G_{k}}$ → it holds for all ${\textstyle G_{i}}$
  • On the boundary ${\textstyle C_{k}}$ of ${\textstyle G_{k}}$ there are the vertices ${\textstyle w_{1},...,w_{p},v_{k},w_{q},...w_{t}}$. ${\textstyle v_{k}}$ covers the vertices ${\textstyle w_{p+1},...,w_{q-1}}$ on ${\textstyle C_{k-1}}$
  • Define the shift of trees ${\textstyle \delta _{i}'}$ in ${\textstyle G_{k-1}}$ by the shift ${\textstyle \delta _{i}}$ in ${\textstyle G_{k}}$
    • ${\textstyle \delta _{i}'=\delta _{i}}$ for all left of ${\textstyle w_{p}}$ (first neighbor of ${\textstyle v_{k}}$)
    • ${\textstyle \delta _{i}'=\delta _{i}+1}$ for all between ${\textstyle w_{p}}$ and ${\textstyle w_{q}}$ (covered by ${\textstyle v_{k}}$)
    • ${\textstyle \delta _{i}'=\delta _{i}+2}$ for all after ${\textstyle w_{q}}$ (last neighbor of ${\textstyle v_{k}}$)
  • After shifting the trees, we attach ${\textstyle v_{k}}$ to its covered subtrees and now move them together
  • Because we can shift in ${\textstyle G_{k-1}}$ with ${\textstyle \delta _{i}'}$, we can shift ${\textstyle G_{k}}$ with ${\textstyle \delta _{i}}$
• Lemma holds for all ${\textstyle G_{i}}$

Implementation

Naive implementation runs in O(n²) time

Towards a faster implementation: ${\textstyle x(v_{k})}$, ${\textstyle y(v_{k})}$ and ${\textstyle x(v_{k})-x(w_{p})}$ can be computed based on the x-y-coordinates of ${\textstyle w_{p}}$ and ${\textstyle w_{q}}$

The x-location of vertices can be represented as a relative x-distance tree. There each vertex stores its y coordinate and its relative x-distance to its tree parent. The relative distance tree is binary

• left child is the first child in the cover tree
• right child is the sibling in the cover tree

The x-distance between ${\textstyle w_{p}}$ and ${\textstyle w_{q}}$ can be computed by traversing the right children from ${\textstyle w_{p}}$ to ${\textstyle w_{q}}$ and summing the relative distances.

When attaching a new ${\textstyle v_{k}}$ to the graph, it needs to be inserted into the x-distance tree (see VL05/127)

• ${\textstyle v_{k}}$ becomes right child of ${\textstyle w_{p}}$ (previously it was ${\textstyle w_{p+1}}$)
• ${\textstyle w_{p+1}}$ is left child of ${\textstyle v_{k}}$ (because it is its first covered node)
• ${\textstyle w_{q}}$ is right child of ${\textstyle v_{k}}$ (because it is a sibling of ${\textstyle w_{p}}$ and ${\textstyle v_{k}}$ in ${\textstyle C_{k}}$) → ${\textstyle w_{q-1}}$ right child is now null

Theorem: Embedded graph → straight line planar drawing on grid in ${\textstyle (2n-4)\cdot (n-2)}$ area.

Theorem: The shift algorithm can be implemented in O(n) time.

Schnyder Realizer

From Euler’s characteristic ${\textstyle |V|-|E|+|F|=2}$ it can be derived for triangulated graphs

• ${\textstyle |E|=3|V|-6}$
• ${\textstyle |F|=2|V|-4}$

With the help of a Schnyder realizer coordinates to vertices can be assigned directly based on combinatorial properties of planar drawings.

Barycentric Representation

Barycentric Coordinates: In a triangle ${\textstyle ABC}$ a position can be described by a triple ${\textstyle (\alpha ,\beta ,\gamma )}$ where

• ${\textstyle \alpha +\beta +\gamma =1}$
• ${\textstyle P=A\alpha +B\beta +C\gamma }$

Barycentric Representation: Is an injective map from each vertex to a triple ${\textstyle (v_{1},v_{2},v_{3})}$ where

• ${\textstyle v_{1}+v_{2}+v_{3}=1}$
• For every edge ${\textstyle (u,v)}$ both its vertices can be compared to any other vertex ${\textstyle x}$. They must both be smaller than ${\textstyle x}$ in one (same) direction. → ${\textstyle x}$ is closer to a corner than both ${\textstyle u}$ and ${\textstyle v}$. → As this holds for all other vertices there is a triangle around the edge where no other vertex can be. (known as the no-no-triangle☝)

Weak Barycentric Representation: The same, but ${\textstyle x}$ can touch the border of the forbidden triangle, but cannot overlap with ${\textstyle u}$, ${\textstyle v}$ or the edge ${\textstyle (u,v)}$.

Lemma: Graph as barycentric representation + a triangle ${\textstyle ABC}$ → planar straight line drawing inside ${\textstyle ABC}$

Proof:

• No vertex inside no-no-triangle for every edge
• Edges cannot cross (see VL06/26)
• For two edges there are four vertices → each vertex has to be larger in one direction than the other edge → e.g. ${\textstyle x_{i}>u_{i},v_{i}}$ → ${\textstyle i,j,k,l}$ are one of ${\textstyle \{1,2,3\}}$
• From the formulas it can be seen that certain assignments to ${\textstyle i,j,k,l}$ cannot be made → only indices of the same edge can be equal → e.g. ${\textstyle \{i,j\}\cap \{k,l\}=\emptyset }$
• When the indices of the same edge are equal (e.g. ${\textstyle i=j=2\implies x_{2},y_{2}>u_{2},v_{2}}$) the edges are separated by a straight line (barycentric coordinates!)

Edge contraction

• Merge two vertices by creating a new one that connects to all of the old neighbors
• Edge is contractible if the edge corners have exactly two common neighbors → graph is still triangulated
• Edge is contractible iff it is not part of a separating triangle

Schnyder Labeling

Definition: Label all internal angles with 1,2,3 such that

• in a face all 1,2,3 exist in counterclockwise order
• around a vertex 1,2,3 are in counterclockwise order without gaps but repetitions are allowed

Lemma: In a triangulated graph with inner vertices, there is an inner vertex connected to a corner that is contractible.

Proof by induction

• Base case: only one inner vertex
• Case 1: The corner is not part of a separating triangle → Take any vertex
• Case 2: Else → Vertices that form the separating triangle are forbidden → Take a vertex from the inside of the separating triangle
  • Induction → Separating triangles are not empty → There will be a vertex to pick

The separating triangles get dissolved from inside out.

Theorem: Plane triangulated graph → Schnyder labeling

Proof by induction

• Base case: Empty triangle has labeling
• Reinstate a contracted edge (uncontract) of an inner vertex → resulting triangles can be labeled trivially
• Induction: Repeat inside one of the new triangles on the same corner → same as before → uncontract the whole graph

Schnyder Realizer

Definition: Schnyder realizer of a plane triangulated graph → Partition & orientation of edges into three spanning trees

• Every vertex is part of the trees → single output, multiple inputs
• Ordering of in and out edges → IN1, IN2, IN3 → IN1, out3, IN2, out1, IN3, out2

• From a Schnyder labeling of a plane triangulated graph → obtain edge orientations and labelings (edge color) → Schnyder Realizer
• Each edge has a vertex that has the same label twice → edge label & direction.
• Each vertex must have an outgoing edge of each type/color

Properties

• Outer edges not colored, and only ingoing edges into the corners: ${\textstyle n-3}$ inner vertices → ${\textstyle 3(n-3)}$ outgoing colored edges → +3 uncolored ones → ${\textstyle |E|=3|V|-6}$ → no more edges left
• Per color there is a connected tree:
  • ${\textstyle n-3}$ edges per color (not for corners) → on a connected graph with ${\textstyle n-2}$ vertices (one corner included) it must be a tree
  • No cycles in each color: empty cycle violates face rule, non-empty cycle entraps other color → would mean smaller cycle inside → recursion
• No criss-crossings of paths: Would violate vertex rule on the second crossing back
• From each vertex there is a path per color to the respective corner → The paths segment the graph into three regions

Lemma: If a vertex lies within a segmented region, its own region (of same color) is strictly smaller.

For a vertex ${\textstyle v}$ with region ${\textstyle R_{i}(v)}$ there are

• ${\textstyle f_{i}(v)}$ faces
• ${\textstyle \eta _{i}(v)}$ vertices inside including one border

It holds:

• ${\textstyle f_{1}(v)+f_{2}(v)+f_{3}(v)=2n-5}$ → ${\textstyle 2|V|-4}$ faces minus single outer face
• ${\textstyle \eta _{1}(v)+\eta _{2}(v)+\eta _{3}(v)=n-1}$ → all vertices except self

Planar straight line drawing

Theorem: Plane triangulated graph + Schnyder realizer → barycentric representation with mapping ${\textstyle f:v\mapsto {\frac {1}{2n-5}}(f_{1}(v),f_{2}(v),f_{3}(v))}$

Proof:

• Property 1: ${\textstyle {\frac {f_{1}(v)}{2n-5}}+{\frac {f_{2}(v)}{2n-5}}+{\frac {f_{3}(v)}{2n-5}}={\frac {2n-5}{2n-5}}=1}$
• Property 2: Not shown?

The required area is ${\textstyle (2n-5)\cdot (2n-5)}$. The time is in O(n).

For the weak barycentric representation use the number of vertices instead. (area = ${\textstyle (n-1)\cdot (n-1)}$)

Sugiyama Framework

For layered graph layout

• Flexible framework
• Sequential optimization of various criteria
• Decomposition into often NP-hard but still practically feasible subproblems → use good heuristics
• Pipeline steps imply restricted solution space

Conventions & Criteria

• many edges pointing upward
• ideally short, straight and vertically edges
• few horizontal layers
• few crossings
• evenly distributed vertices

Steps

1. Break cycles: directed input graph → DAG
2. Assign layers
3. Minimize Crossings (+ dummy vertices)
4. Position vertices
5. Draw edges: turn back reversed edges

Does not guarantee an optimized drawing → each step depends on its predecessor's output

1. Break cycles

Pick one edge per cycle and flip it → When possible the same edge for multiple cycles

Algorithm idea for Feedback Arc Set:

• Find "max acyclic subgraph"
• Invert the rest

This is NP-hard → find a heuristic.

Heuristic 1

1. A is empty set
2. Go over all vertices
3. More incoming edges → add them to A
4. Else More outgoing → add them to A
5. Remove vertex and its edges

• The graph with only edges from set A is a DAG → the remaining edges are the feedback set → combine to get D
• For any cycle a first member vertex is picked → Either the incoming or outgoing edges are flipped → the cycle is broken → D is acyclic
• At most half of the edges can be picked per vertex → at most half of all edges get flipped
• Running time O(|V| + |A|)

Heuristic 2

1. A is empty set
2. While graph not empty take vertex ${\textstyle v}$
   1. Remove all sinks and add their incoming edges to A
   2. Remove isolated vertices
   3. Remove all sources and add their outgoing edges to A
   4. If graphs is still not empty
      1. Pick vertex with largest ${\textstyle \#outgoing-\#incoming}$ (most source-like)
      2. Remove it and add outgoing edges to A

For step 4: There will always be a source-like vertex with ${\textstyle \#outgoing-\#incoming\geq 0}$ due to handshaking lemma, either all are 0, or one is <0 then there is one with >0

Lemma: Connected directed graph without 2-cycles → Heuristic 2 computes an edge set A with ${\textstyle |A|\geq |E|/2+|V|/6}$ in O(|A|) time

When using buckets to sort vertices by their degree, with buckets for sources, sinks and isolated, we can run the algorithm in O(|A|) time, as removing a vertex can be done in deg(v) time.

2. Assign Layers

DAG as input → disjoint sets of vertices in layers → all edges go strictly upwards (lower to higher layer) → define y-coordinate for each vertex

Optimization Goals:

• Minimize layers
• Minimize width
• Minimize longest edge
• Minimize total edge length

Height Minimization

Idea: Put all predecessors of a vertex in the DAG below it → longest simple path is layer of vertex → total height is minimal

Algorithm

1. Assign source vertices to first level
2. While graph not empty
   1. Remove sources and find new source vertices
   2. Place new sources on next level

Runs in O(|V| + |A|) time

Minimizing total edge length

Formulate as ILP and use a solver. (generally NP-hard problem)

Fixed width layer assignment

Place vertices on minimized number of layers with max width of B → equivalent to job scheduling problem with dependencies between tasks → Use MPCS (Minimum Precedence Constrained Scheduling)

Theorem: Given ...

• n jobs ${\textstyle J_{i}}$ of equal length
• Precedence relation ${\textstyle J_{i}<J_{j}}$
• B identical machines

... it is NP-complete to decide if a schedule of at most length T exists, even with T= 3.

Proof by reduction:

• Reducing NP-complete problem ${\textstyle Clique\leq MCPS}$ with T=3 shows MCPS is NP-hard as well
• Lots of math here

Theorem: There is a polynomial time approximation for MCPS that approximates with a ratio of ${\textstyle \leq 2-{\frac {1}{B}}}$

The MCPS problem can be approximated using the list scheduling algorithm.

• Whenever machine is free assign first feasible job to it
• Else machine remains idle
• Proof uses the fact that at least one machine is never idle

3. Crossing Minimization

• Local optimization by swapping → Output of one layer influences the next
• Layer assignment of DAG → vertex placement per layer with minimized crossings
• NP-hard for only 2 layers (OSCM)
  • No polynomial time approach to optimize across multiple layers
  • Usually optimize adjacent layers iteratively
  • Insert dummy edges for long edges
• Level planarity (is there a crossing free solution?) can be tested in O(n)

One-sided Crossing Minimization (OSCM)

2 layered graph + vertex ordering → vertex ordering with minimal crossings

Observations:

• Crossings only depend on ordering not final position
• Number of crossings between two vertices' edges only depends on which vertex comes first

Definition: Crossing Value ${\textstyle c_{uv}}$ → for a vertex pair ${\textstyle u}$ and ${\textstyle v}$ in the second layer where ${\textstyle u<v}$ count the number of possible pairs of neighbors in the first layer where the ordering is swapped.

Observation: ${\textstyle c_{uv}+c_{vu}\leq |N(u)|\cdot |N(v)|}$

• Crossing number of graph G with ordering ${\textstyle x_{1},x_{2}}$ → ${\textstyle cr(G,x_{1},x_{2})=\sum _{x_{2}(u)<x_{2}(v)}c_{uv}}$
• for fixed ${\textstyle x_{1}}$ → ${\textstyle opt(G,x_{1})=min_{x_{2}}cr(G,x_{1},x_{2})\geq \sum _{u,v\in L_{2}}min\{c_{uv},c_{vu}\}}$
• ${\textstyle cr(G,x_{1},x_{2})}$ can be computed in ${\textstyle O(n\cdot log(n))}$ time

Iterative Crossing Minimization

Iteratively optimize a graph with multiple layers

1. Random ordering for first layer
2. Repeat until no further improvement
   1. For all layer pairs bottom up: Optimize next upper based on fixed lower
   2. For all layer pairs top down: Optimize next lower based on fixed upper
3. Restart step 1 with different random first layer → Return best

Barycenter OSCM

Idea: Few crossings when vertices are close to their neighbors

${\textstyle x_{2}(u)={\frac {1}{|N(u)|}}\sum _{v\in N(u)}x_{1}(v)}$ → Average the x positions/ordering indices of all neighbors in the layer below

• simple & fast
• usually very good results
• Can find optimum if it is level planar (aka ${\textstyle opt(G,x_{1})=0}$)
• The solution can be ${\textstyle \theta ({\sqrt {n}})}$ worse than optimal solution for some graphs → Bad because quality/approximation factor is not constant but depends on input size

Proof for approximation factor (see VL07/86):

• Vertex ${\textstyle u}$ has K neighbors in lower level
• Vertex ${\textstyle v}$ has K+1 neighbors in lower level where one vertex is placed far out (K²)
• With ${\textstyle v<u}$ we would have K crossings due to the far away vertex
• With ${\textstyle u<v}$ we would have K² crossings
• Due to the distance K² → we set ${\textstyle u<v}$ → this is worse by factor K
• We can see: ${\textstyle n=\theta (K^{2})}$ → ${\textstyle K=\theta ({\sqrt {n}})}$

Median OSCM

Idea: Set position to median of the neighbors

1. Set position to median of x positions/ordering indices of all neighbors in the lower level
2. If no neighbors → place at index 0
3. If two vertices at same position and different degree parity → place odd degree to the left
4. Else place arbitrary

Run time in O(|E|)

• simple & fast
• mostly good performance
• Can find optimum if it is level planar (aka ${\textstyle opt(G,x_{1})=0}$)
• Constant factor-3 approximation

Approximation factor: lots of math and crazy substituting

ILP OSCM

• Integer Linear Programming Model
• Finds optimal solution
• Possibly not in polynomial time
• Suitable for small/medium graph
• Use binary variables ${\textstyle x_{uv}}$ to select orderings between all vertex pairs
• Variables select either ${\textstyle c_{uv}}$ or ${\textstyle c_{vu}}$ to sum up over all pairs
• Model transitivity ( ${\textstyle u<v\land v<w\implies u<w}$ ) using a linear inequality (like a XNOR)

4. Coordinate assignment

Edge straightening: Minimize deviation from a straight line for edges consisting of dummy vertices

Idea:

• Compute ${\textstyle a}$ as a straight line from bottom to top vertex → ${\textstyle a_{i}}$ is ideal position on level i
• Minimize the total quadratic deviation ( ${\textstyle \min \sum (x_{i}-a_{i})^{2}}$ )
• Ensure minimal spacing between vertices on same layer

Properties

• Solving can be expensive
• Possibly exponential width

5. Draw edges

• Flip edges back to their original direction
• Remove dummy vertices
• Optionally draw Bezier curves for edges

Orthogonal Drawings

Conventions & Criteria

• few crossings
• few bends
• isomorphic sub-structures are drawn the same

TSM Approach

TSM: Topology - Shape - Metrics

1. Topology: Reduce crossings → Combinatorial Embedding
   1. Planarization → Insert dummy nodes for crossings
2. Shape: Minimize bends → orthogonal representation
3. Metrics: Minimize area → planar orthogonal drawing

Bend Minimization with Fixed Embedding

Geometric Bend Minimization: Planar graph + embedding → orthogonal drawing with same embedding and minimal bends

Combinatorial Bend Minimization: Planar graph + embedding → orthogonal representation with same embedding and minimal bends

Orthogonal Representation

Orthogonal representation of graph G ${\textstyle H(G)}$ consists of orthogonal representations for all of its faces ${\textstyle H(f)}$

Face representation:

• Clockwise ordered set of edge description tuples ${\textstyle (e,\delta ,\alpha )}$
• ${\textstyle e}$ → name of edge
• ${\textstyle \delta }$ → String of 0s and 1s describing sequence of bends (0 = right, 1 = left)
• ${\textstyle \alpha }$ → Counterclockwise angle between this and next edge (90° steps in radiants → ${\textstyle {\frac {\pi }{2}},\pi ,{\frac {3\pi }{2}},2\pi }$)

Setting ${\textstyle \alpha =2\pi }$ is useful for turning around on degree 1 vertices

Correctness:

1. ${\textstyle H(G)}$ corresponds to all faces
2. For two faces sharing an edge → the bending sequence ${\textstyle \delta }$ of common edge is reversed and inverted → because going through the edge in different directions (left turn becomes right turn)
3. For an edge representation ${\textstyle r}$ we compute ${\textstyle C(r)=|\delta |_{0}-|\delta |_{1}+2-{\frac {2\alpha }{\pi }}}$. The sum of all ${\textstyle C(r)}$ of an inner face is 4, for the outer one is -4.
4. For each vertex the sum of incident angles is ${\textstyle 2\pi }$

Combinatorial Bend Minimization using Flow Network

• One unit of flow → angle of ${\textstyle \pi /2}$
• Flow vertex → face: angle in vertex
• Flow face → face: edge bends

General Flow Networks

Inputs:

• directed graph
• lower bound ${\textstyle l}$ and capacity ${\textstyle c}$ per edge (min & max flow)
• production/consumption ${\textstyle b(u)}$ per vertex → sum of all ${\textstyle b(u_{i})}$ is 0

Valid flow satisfies:

1. Flow at each edge is within bounds
2. Flow at each vertex ${\textstyle u}$ is ${\textstyle b(u)}$ (outgoing - incoming)

Cost function: define cost per edge → Minimum cost flow minimizes total cost

Bend Minimization

Create flow graph N

• Each vertex in G → vertex in N
• Each face in G→ vertex in N
• Each vertex v incident to face f in G → in N edge from v-vertex to f-vertex
• Each two adjacent faces f,g in G → two edges between f- & g-vertices (one per direction)

Creates directed multigraph with productions:

• Every v-vertex → production ${\textstyle b(v)=4}$
• Every inner face f-vertex → ${\textstyle -2\cdot (deg_{G}(f)-2)}$
• Outer face f-vertex → ${\textstyle -2\cdot (deg_{G}(f_{0})+2)}$

Note: ${\textstyle d_{G}(f)}$ is the count of half-edges along boundary (count degree 1 vertices twice)

Total flow sums up to 0 due to Euler's formula (see VL10/34).

Bounds:

• Flow between face vertices is within ${\textstyle 0,\infty }$ and costs 1
• Flow between v-vertex and f-vertex is within ${\textstyle 1,4}$ and costs 0

Summary

Theorem: Planar embedded graph has valid orthogonal representation with k bends iff the flow network has valid flow with cost k.

Proof: valid flow → valid representation:

1. All faces are represented in flow graph
2. Use construction of bending sequence as ${\textstyle \#0=X(f,g)}$ and ${\textstyle \#1=X(g,f)}$
   1. Sequence only contains 1s or 0s → Reversing ✅
   2. Sequence is inverted on the other face
3. Math
4. Set angle to ${\textstyle X(v,f)\cdot {\frac {\pi }{2}}}$
   1. Production of each vertex is 4 → sum is ${\textstyle 2\pi }$

Proof: valid representation → valid flow:

• Use the same constructions
• Just works?

Results

• Use min-cost-flow to solve bend minimization
• Planar min-cost-flow solvable in ${\textstyle O(n^{3/2})}$
• Without embedding → bend minimization NP-hard

Compaction

Find compact orthogonal layout that realizes an orthogonal representation

Rectangular faces

Special case with only rectangles → guarantees for min total edge length, min area

Flow Network

Use horizontal flow network ${\textstyle N_{hor}}$ to minimize edge length

• Each face in G → vertex in N + one source & one sink vertex
• For each horizontal segment of adjacent faces where f is below g → edge from f-vertex to g-vertex
• Connect source and sink vertex to bottom and top segments
• Form loop from sink to source

Set bounds for N:

• Each edge has flow within ${\textstyle 1,\infty }$ → lower bound enforces flow > 0
• Each edge has cost 1
• Each vertex has production/consumption of 0 → All flow goes in a loop

Flow per edge in N describes the length of the respective segment between faces in G.

Same for vertical flow network ${\textstyle N_{ver}}$

Compute total area/lengths

1. Total edge length is the sum of all individual flows in ${\textstyle N_{ver}}$ and ${\textstyle N_{hor}}$ minus flow through the t-s-edges
2. Total area is ${\textstyle w\cdot h}$. The length per side is the flow through the t-s-edge.

Theorem: Minimum cost flow induces a valid orthogonal layout → Area and total edge length can be computed from the flows.

Rectangularization

Convert a non rectangular face into a set of rectangles. Extend each edge to the closest orthogonal opposite edge → project vertex and subdivide the face.

Inner faces:

1. Replace bends with dummy vertices
2. Assign value to bends: left= 1, right= -1, straight= 0
3. For each edge
   1. Sum up bend values
   2. Stop when reaching 1 → select edge following last bend
   3. Project a new vertex on to selected edge

Outer face:

1. Same setup as above
2. Add outer rectangle that envelopes the face
3. For each edge
   1. Same as above
   2. If no edge is found (traversed full boundary with < 1) → project to outer rectangle

All faces are rectangles → Apply flow network → But area not minimal → NP-hard

Complexity of Layout Compaction

Theorem: Graph + orthogonal representation → NP-hard to test for layout of area at most K.

Proof: Reduce SAT → Layout compaction

• Create pistons for all variables
• Create common border → Restrict piston movement to up and down
• Create belt that restricts pistons to top or bottom position → binary value
• Connect pistons horizontally for each equation
• Create gadgets for each variable in each equation → ${\textstyle x}$, ${\textstyle {\bar {x}}}$, ${\textstyle \emptyset }$
• Route a chain of "A"s through the equation tunnels
• The graph has a minimal area of ${\textstyle K=(9n+2)\cdot (9m+7)}$ if there is a satisfying assignment for the equations → herby solving the SAT problem

Lower Bounds for Planar Grid Drawings

Determine tight upper and lower bounds for the drawing area → Upper bounds ${\textstyle (n-2)\cdot (n-2)}$

Lower bounds: Trivial lower bound → n

Path width

Definition: Vertex ordering ${\textstyle \sigma }$ → Split into left group of increasing size and right group of shrinking size → Every time count the number of vertices with connections from left to right set → Maximum is the vertex separation number ${\textstyle vs(\sigma )}$

Definition: Graph has pathwidth ${\textstyle pw(G)\leq k}$ iff graph has a vertex ordering ${\textstyle \sigma }$ with ${\textstyle vs(\sigma )\leq k}$.

Theorem: Planar graph → grid drawing height ${\textstyle \geq }$ pathwidth pw(G)

Testing whether a graph has pathwidth k is NP-hard.

Visibility Representation

Definition: Graph G → Each vertex is represented as a horizontal box. Each edge is a vertical or horizontal segment connecting its vertex-boxes. No intersections.

Lemma 1: Graph planar grid drawing of height h → Visibility representation of height h

Lemma 2: Graph with visibility representation of height h → ${\textstyle pw(G)\leq h}$

Proof: Find a vertex ordering ${\textstyle \sigma }$ with ${\textstyle vs(\sigma )\leq h}$ in visibility representation of height ${\textstyle h}$

• Construct ordering ${\textstyle \sigma }$ of boxes/vertices: left-to-right and top-to-bottom
• Draw line anywhere through a box
• At most one vertex/box per row can connect across the line → at most h vertices connect → ${\textstyle vs(\sigma )\leq h}$

Theorem: Planar graph G with ${\textstyle pw(G)}$ → every grid drawing has height ${\textstyle h\geq pw(G)}$

Proof: Using Lemma 1 and 2

• Assume there is a drawing with height ${\textstyle h<pw(G)}$
• with Lemma 1 ${\textstyle \implies }$ there is a visibility representation with height ${\textstyle h}$
• with Lemma 2 ${\textstyle \implies }$ ${\textstyle pw(G)\leq h<pw(G)}$
• contradiction

Special Case: Trees

Observation: Rooted tree with height ${\textstyle h}$ → ${\textstyle pw(T)\leq h}$

Proof: By induction

• Base case: Single vertex → ${\textstyle h=0}$, ${\textstyle pw(T)\leq 0}$
• Induction: Each subtree ${\textstyle T_{i}}$ has height ${\textstyle h-1}$ and therefore ${\textstyle pw(T_{i})\leq h-1}$

Every root has its subtrees to the right → h (subtree-)roots have to go from left to right half of the ordering → Splitting in the middle has separation h (see VL12/27)

Lemma 3: Tree T has vertex v → removing v decomposes T into ${\textstyle \geq 3}$ subtrees → each subtree ${\textstyle T_{i}}$ has ${\textstyle pw(T_{i})\geq k}$ → original T has ${\textstyle pw(T)\geq k+1}$

Proof:

• ${\textstyle pw(T)\geq K}$ trivially → because the subtrees already have ${\textstyle pw(T_{i})\geq k}$
• But assume ${\textstyle pw(T)<k+1\implies pw(T)=k}$
• Therefore there is an ordering with ${\textstyle vs(\sigma )=k}$
• When reintroducing the vertex ${\textstyle v}$ → anywhere it is placed for the subtree in the middle the separation goes up to ${\textstyle k+1}$
• Contradiction → separation is at least ${\textstyle k+1}$ → ${\textstyle pw(T)>=k+1}$

By combining the observation (${\textstyle pw(T)\leq h}$) and Lemma 3 (${\textstyle pw(T)\geq h}$) → for these trees it holds ${\textstyle pw(T)=h}$

Theorem: Tree has ${\textstyle pw(T)\leq k}$ iff you can delete a path of vertices such that every tree in the resulting forest has ${\textstyle pw(T_{i})\leq k-1}$. This path is called "main path"

Proof: skipped

Theorem: Rooted tree → Planar grid drawing with height ${\textstyle h=2pw(T)}$

Proof: skipped

Summary

• Every planar grid drawing has height ${\textstyle h\geq pw(G)}$
• For every rooted tree there is a planar grid drawing with height ${\textstyle h=2pw(T)}$
• Pathwidth gives only for trees a tight lower bound.

Octolinear Graph Drawing: Metro Map Layout

• Goal: easy-to-use visual navigation aid for train passengers
• Topology over topography
• Distorts scale and geometry
• Computationally challenging → Still manual process

Task

Subtasks:

• Rendering and design choices (colors, symbols, ...)
• Network layout (geometry, placement, ...)
• Station labeling (where to position labels)
• Metro line routing (route the metro lines through the network)

Formalized problem:

• Geometrically embedded graph of the railway network
  • Station = vertices, Edges = rail links
• Set of paths on G
  • Metro lines

Design Rules

1. Do not change network topology
   1. No new crossings
   2. No change in circular vertex order
2. Restrict edge orientation → e.g. octolinear
3. Draw metro lines simple & monotone
   1. Avoid bends
   2. Prefer obtuse angles
4. Lines pass straight through interchanges
5. Use large angular resolution in station
   1. Distribute edges evenly for balanced appearance
6. Minimize geometric distortion and displacement
   1. Try to maintain geographic topography
7. Use uniform edge lengths
   1. Geographic distance less important
   2. Station "hop-distance" more important
8. Keep unrelated features apart → Minimum clearance
9. Avoid large empty spaces
   1. Balance feature density
   2. Possibly fill gaps with legends

Rules conflict with each other and need priorities

Theorem: Embedded graph (vertex degrees ${\textstyle \leq 8}$) → bend minimization with preserving topology & octolinearity is NP-hard

Schematization Approaches

Path-Based

Constraints:

• (R2) Oriented edges
• (R6) Displacement within bounds

Optimize:

• (R3) Minimize number of segments along edge

Theorem: Path with length n + orientation set C → Heuristic schematization in ${\textstyle O(|C|\cdot n)}$ time.

Theorem: Monotone path + orientation set → schematization in O(n²) + solve(LP) time that...

• Preserves orthogonal order (relative north-south-east-west relationship vertices),
• Minimum slope deviation and total length

Thorem: Non-monotone route sketch with orientation set where angles <90° → NP-hard

Pros:

• Polynomial running time
• Orientations and displacement bounds guaranteed
• Bend minimization
• Works with metro maps → Schematize each line individually

Cons:

• (R1) No guarantee on network topology
• Too little distortion/displacement for metro maps

Force-Based

Octolinear

Charged particles model with additional forces for design rules

Setup:

• (R1) Only apply vertex moves that preserve topology
• (R2) Define octolinear magnetic field attracting edges
• (R3) Contract degree-2 vertices into weighted edges
• (R7) Spring lengths model uniform edge lengths
• (R8) Vertex repulsion model feature clearance

Labels are placed in an unrelated second step

• (R1) Guarantees topology
• Slower than path based (but still ok)
• No strict octolinearity
• Unbalanced edge lengths
• Bends in interchanges
• No restriction on distortion

Bezier

• (R1) Guarantees topology
• Considers almost all rules
• Good for small and medium sized instances
• Difficult for complex networks

Local

• Define layout quality function (like loss function)
• Improve layout iteratively by optimizing quality function
• Move vertices individually on the grid
• Optimize with: hill climbing, simulated annealing, ant colony, ...

Pros:

• Flexible framework (can integrate new criteria)
• New methods show improved visual layout quality (aka they are better?)
• Integrates both layouting & labeling

Cons:

• Optimizes criteria but does not enforce
• Local minima
• Slow

Mixed-Integer Linear Programming

• Find exact optimal solution
• Split design rules into hard and soft constraints
  • Hard → Constraints (linear inequalities)
  • Soft → Loss/Objective function (linear function)
• Integrate labeling
• Use existing solver programs

Hard Constraints

• (R1) Preserve topology & planarity
• (R2) Octolinearity
• (R7) Minimum edge length
• (R8) Minimum feature separation

Soft Constraints

• (R3+R4) Minimize bends
• (R6) Minimize distortion
• (R7) Minimize edge length

Linear Programming

Linear programming (LP) is an efficient optimization method for

• Linear constraints
• Linear objective function
• Real valued variables

Mixed-Integer Programming (MIP)

• Include binary & integer valued variables
• NP-hard
• Often used

Theorem: Metro map can be modeled as MIP → as described previously.

Model

Definition

• 8 angle sectors per vertex
• 2 euclidean coordinate systems (with 0° and 45° rotation)

Hard Constraints:

• Select direction only from original sector or its direct neighbors
• Define inequality formulas for each sector
  • Binary variable either selects a specific value or ${\textstyle M}$ on the right side → enables the constraint
  • The formulas enforce max and min x/y movement on the two coordinate systems
  • Enforces slope/direction and edge length

Number of constraint variables in O(n²).

Objective function to optimize:

• Cost of bends
  • In each vertex compare incoming/outgoing sector
  • Acute angles are more expensive
  • Sum for all edges over all vertices
• Cost of length
• Cost of relative position deviation

Labeling

• Prevent labels from overlapping
• NP-hard problem
• Integrate it into the layout problem
  • Define "keep out zone" as parallelogram → flipping allowed
  • Put labels inside the zone after layouting

Pros/Cons

Pros:

• Flexible but hard to adapt
• Includes labeling
• High quality
• Theoretical guarantees

Cons:

• Slow (unpredictably so)
• No proof for optimality with large labeled networks
• Quality depends on model specification

Least-Squares

• Compute squared energy terms (deviation) for vertex position & slopes
• Iteratively optimize/minimize energy
• Very fast & good quality
• Constraints only guaranteed when deviation/energy is zeroed

Grid-Based

• Place vertices on octolinear grid
• Route edges via shortest paths
• Bends and path lengths → edge costs
• Very fast & good quality
• No labeling

Summary

• 2 decades of research
• tradeoff: speed vs quality
• can help human designers → semi-automated process
• better special-purpose maps

Constrained Planarity

Edge crossings are bad for readability

Drawing planar graphs with additional information to visualize → Constrained planarity drawing

Level Planarity

Graph with level assignment, draw planar with

• place vertices on their level
• edges are (strictly) y-monotone

Properties

• Proper: No edges across level (use dummy nodes)
• Single-Source: Graph has only one node with no nodes under it → one common source at lowest level

PC- & PQ-Trees

PC-Trees represent a circular ordering of their leaves.

Consecutive Ones

• Matrix with all zeros
• Columns named by the variables
• Each row is a constraint → every variable sets a one in its column
• Reorder the columns such that in each row the ones are next to each other

Circular Consecutive Ones: Columns can wrap around to fulfill the consecutiveness

PC-Tree Update

1. Leaves
2. P-Node: Children ordered arbitrarily → All possible permutations
3. C-Node: Children ordered circularly → Children has fixed prede-/successor

Update: Find a new tree where red leaves are consecutive

Definition: Terminal Edge → Both subtrees contain red and black leaves

Lemma: PC-Tree has consecutive ordering → Terminal edges form path

1. Compute path of terminal edges
2. Order path with black and red nodes on opposite sides of the path
3. Replace path with single C-Node → Duplicates nodes on the path
4. Contract C-Nodes into central node
5. Contract nodes of degree ${\textstyle \leq }$ 2

Run time of update is upper bounded by number of red nodes.

PC-Tree solves circular consecutive ones problem → Insert an all zero column (s-node) to solve regular consecutive ones.

PQ-Trees

• Represent a linear ordering of leaves → Similar P and Q nodes
• Rooted
• Time equivalent with PC-Trees

Both types can simulate each other

Testing Level Planarity

Lemma: Lower/Upper neighbors must be consecutive → planar drawing

The nodes needed to be consecutive can be represented as restrictions → consecutive ones problem

Theorem: Single source graph → Test level planarity in O(n) time

Theorem: General graph → Test level planarity (presumably) in O(n) time

Clustered Planarity

Graph with clustering → planar drawing with

• Clusters represented by hole-free region
• Clusters do not cross unrelated edges/clusters → Single blob with in/outputs

Application: UML

Level Planarity Reduction

Theorem: Level planarity → reducible to Cluster Planarity

Proof:

• Level ${\textstyle L_{i}}$ is sandwiched by ${\textstyle L_{i-1}}$ and ${\textstyle L_{i+1}}$
• Duplicate every level and make parallel connections between the copied vertices
• All lower levels from & including lower copy of ${\textstyle L_{i}}$ is part of cluster A
• All upper levels form & including upper copy of ${\textstyle L_{i+1}}$ is part of cluster B
• Now everything is inside clusters except the border region across ${\textstyle L_{i}}$ to ${\textstyle L_{i+1}}$
• Run cluster planarity → Same as level planarity for ${\textstyle L_{i}}$ & ${\textstyle L_{i+1}}$

Cluster Decomposition Tree

• Outside: Represent clusters as single vertices
• In each cluster: Point all outgoing edges into a single vertex
• Same rotation order → Like a portal
• Inside the cluster the portal vertex can be represented by a PC-Tree
• Convert PC-Tree to a constrained embedding (see example VL13/124)
• Replace the cluster in the original graph with the embedding
• Check for planarity → Cluster planarity

Theorem: Graph is cluster planar iff there is a planar cluster embedding where rotations line up

Theorem: Clustered Planarity of c-connected graphs can be tested in O(n) time.

Level und Cluster Planarity are in P. SEFE-3 is NP. SEFE-2 is ?.

Contact Graphs

Definition: Area cartogram → map where areas of regions represent an external value (e.g. population)

Conventions & Criteria

• Shapes recognizable
• Comparable
• Relative positions
• Correct adjacencies
• Small area error

Rectangular

• Regions are represented as rectangles
• Goal: rectangles should have specified area
• Trade-off between adjacencies/area

Input:

• Adjacencies between regions
• Some value of region → influences area

Output:

• Distorted map
• Area-proportional contact representation

Note: It is not always possible to guarantee correct areas and adjacencies.

Contact Graphs

• Every planar graph has disk contact representation
• Every contact graph of non-overlapping shapes is planar
• Testing if planar graph has disk contact representation with preset areas → NP-hard
• Planar graph can be represented by rectangular contacts iff
  • 4-connected → No separating triangles → would require L-shapes
  • Internally triangulated

Theorem: There are plane triangulated graphs that need T-shapes (rectilinear polygon with at least 8 corners)

Proof:

• Very specific graph with
  • 7 separating triangles with each a vertex inside
  • 6 regular vertices
• Each vertex inside a separating triangle forces an L-shape with an additional inset
• 7 triangles → 7 insets → only 6 regular vertices
• One vertex represented by a box with 2 additional insets
• T-shape with 4 additional corners → 8 corners

Canonical Order & Schnyder Realizer

Convert Canonical Order to Schnyder Realizer:

1. For each vertex in the order
   1. Point edge to first neighbor in ${\textstyle C_{i-1}}$
   2. Point edge to last neighbor in ${\textstyle C_{i-1}}$
   3. Point edge to successor with highest index

Convert Schnyder Realizer to Canonical Order:

1. Invert edges from 2 of the 3 spanning trees
2. Compute topological order of the DAG (consume & remove the sources)

8-sided Rectilinear Cartograms

Definition: Area Universality: Combinatorially equivalent layout can be used for any assigned area values → correct area and adjacencies guaranteed

Theorem: Rectangular layout is area-universal iff one-sided

Definition: One-Sided layout: Every line touches a full-single rectangle on at least one side

3-Phase algorithm:

1. Create contact representation made of Ts
2. Convert Ts to T-shaped polygons
3. Stretch polygons to fill holes

1. Phase: T-contact representation

1. Create Schnyder Realizer + Canonical Ordering
2. For every vertex in canonical order
   1. Draw flipped T on new level where
   2. Horizontal line touches vertical lines of both spanning tree parents
   3. Vertical line to level of third spanning tree parent

2. Phase: Lambda-fattening

Grow the T-Lines into T-shaped polygons with thickness ${\textstyle \lambda }$ within ${\textstyle 0<\lambda <{\frac {1}{2}}}$

3. Phase: Remove Holes

• Frame everything with a box
• For every hole find an inset/concave corner of a T-polygon → Select this polygon
• Stretch the select polygon to fill the hole

Area Universality

Theorem: The resulting layout is area universal and has only polygons with complexity ${\textstyle \leq }$ 8

Proof:

• Split T-polygon into 4 rectangles
• Those 4 rectangles are one-sided → area universal
• Distribute are of each region arbitrarily among its 4 rectangles

Opening Question

In previous years Prof. Nöllenburg often began the exam with an opening question like "What is a graph?", "What do you know about the graph drawing problem?".

• What is a graph?
  • Tuple of vertices and edges
  • Set of vertices
  • Set of edges -> Connect vertices
  • Represent as set, adjacency list, adjacency matrix, drawing
• Layout Problem / Graph visualization problem
  • Based on graph find drawing that
  • ...complies with conventions (hard constraints)
  • ...optimizes aesthetics/quality (soft constraints)
  • ...satisfies partial/local constraints
• Quality Criteria
  • Conventions
    • straight-lines
    • orthogonal edges
    • grid drawing
    • crossing free
  • Aesthetics/Quality
    • Number of crossings
    • Number of bends
    • Uniform edge length
    • Total area/length
    • Symmetries...
  • Partial/Local constraints
    • Constraint (relative) position of some vertices
    • Group vertices