Monday, May 06, 2024 (Lecture 1): Administrivia. Intro to planar graphs
Main question of the course: given a graph class, what problems
can be solved easy/easier than on arbitrary graphs?
Some graph classes. Planar graphs. Interval graphs. Partial k-trees.
Warm-up example: Finding a maximum weight independent set in a path.
Administrivia. How grades are determined.
Planar graphs. K4 is planar, K5 and K3,3 are not.
Four tools to solve problems in planar graphs:
(a) use some property of planar graphs,
(b) use the planar embedding,
(c) try the problem in the dual graph,
(d) use the planar separator theorem for a divide-and-conquer approach.
Baby example: finding maximal clique in planar graphs.
Wednesday, May 08, 2024 (Lecture 2): Simple algorithms for planar graphs
How to `give' a planar graph drawing?
Faces. Facial circuits. Rotation system. This is
easily stored with incidence list data structure.
Spherical embedding. Can read facial circuits from this alone.
Planar embedding = spherical embedding + one face.
Can show (no proof) that a planar embedding
determines a planar drawing. From now on, `planar
graph' means `given with a planar embedding'.
Example for how to use a planar drawing: Menger problem. Right-hand search
is DFS with next edge chosen based on rotation. Using this to find
paths in linear time. Sketch of why this finds the maximum
set of paths.
Euler's formula. Proof. Lots of consequences.
Every simple connected
planar graph with at least 3 vertices has at most 3n-6 edges.
K5 is not planar.
Every simple connected
planar bipartite graph with at least 3 vertices has at most 2n-4
edges. Therefore K5 and K3,3 are not planar.
Friday, May 10, 2024 (Lecture 3): NP-hardness and planarity
Algorithmic consequences of m≤ 3n-6:
Simplify/speed up algorithms. Example: Shortest path.
Find min-degree order, then every vertex has indegree at most 5.
Coloring. Every planar graph can be colored with 6 colours.
Proof via min-degree-ordering and greedy-algorithm for colouring.
Adjacency queries. Can be done in O(1) time by storing
min-degree-ordering.
Finding maximum cliques in planar graphs in linear time, using the
min-degree ordering.
Some problems that remain NP-hard in planar graphs, and how to prove this.
Method 1: crossing gadget to remove a crossing without affecting solutions
of the problem. Example: 3-coloring. The crossing gadget and its colorings.
How to insert the crossing gadget into a suitable drawing. In consequence,
3-coloring is NP-hard even in planar graphs
Similar approach for 3SAT. The graph of a 3SAT instance. Planar3SAT =
instances of 3SAT where this graph is planar. Theorem: This is NP-hard.
Proof via crossing gadget (no details).
Method 2 for proving NP-hardness in planar graphs: create
reductions that preserve planarity. Example: Independent
Set. Reduction from 3-SAT to Independent Set. Observe: if 3SAT
graph is planar, then so is constructed graph.
In consequence, Independent Set is NP-hard even in planar graphs of
max-degree 3.
Week 2
Monday, May 13, 2024 (Lecture 4): Dual graphs. Maximum Flow in st-planar graphs
Maximum-flow problem.
(s,t)-cuts and their values. The MaxFlowMinCut theorem (no proof).
Now: Maximum flow in planar graphs.
Detour: Dual graphs. Definition (this depends on the fixed
spherical embedding). Some properties. For any problem in
planar graph, we should always also consider what the corresponding
problem in the dual graph is.
Back to MaxFlow in planar graph. Really solve minimum cut instead.
Intuition: (s,t) cuts become closed curves that separate s and t.
In dual graph, these are cycles that that separate s and t. Special case here only:
both s and t on outer-face.
Rather than finding cycles, split outer-face and find shortest
path. Proof of correctness via recovering
a flow from distances in dual. This flow-value
matches the cut-value, so both are optimal.
Wednesday, May 15, 2024 (Lecture 5): Maximum Flow in planar graphs. Maximal planar graphs
Maximum flow if s and t are not on one face. General idea for embedded graphs:
Can `slice open' to achieve some properties. Specific for MaxFlow, slice dual
along path P from near s to near t. Any minimum (s,t)-cut is a shortest cycle C in dual
graph, hence intersects P, hence becomes a shortest path between a pair {si,ti} that results
from slicing. So new problem is to find all shortest paths for k vertex-pairs that are
all on one face (and in order). Solving this via divide-and-conquer in O(n log2 n) time.
We are skipping Chapter 6 for now, but you can use without proof that planar graphs
can be recognized (and a planar embedding found) in linear time.
Maximal planar graphs. All faces must be triangles, otherwise we could get a planar K5.
Corollary:
Can make a graph triangulated by adding edges. This can be
done in linear time (no details).
Triangulated graphs. Equivalences. Triangulated graphs have 3n-6 edges, and 2n-4 faces.
They are also 3-connected. Detour into connectivity. In planar graphs, minimal
cutting sets correspond to nooses that have vertices on both sides (no proof). So if
not 3-connected then we have a face with 4 or more vertices. Consequence: Triangulated
graphs have a unique spherical embedding (up to reversal of all rotations).
Friday, May 17, 2024 (Lecture 6): Canonical ordering and applications
The canonical order. Definition and examples. Every triangulated
graph has a canonical order. Proof, by actually finding a canonical
order for any triangulated disk.
Properties of canonical ordering. The predecessors of vk+1
form an interval on the outerface of graph Gk. The canonical
ordering can be found in linear time (no details).
Application I: edge-parition into forests. How to label the
edges. Why each set of edges is a forest.
Application II: Visibility representations and grid-minors.
Every planar graph has a visibility representation in an nx3n-grid.
How this implies that planar graphs are minors of grids.
Invariants to maintain while adding vertices. How to add a vertex.
Application III: Every planar graph has a planar straight-line drawing.
Invariants to maintain while adding vertices. How to add a vertex.
With appropriate modifications we can even achieve integer coordinates
that are linear (no details).
