Tuesday, May 12, 2020 (Lecture 1): Intro to planar graphs
Administrivia. How grades are determined. Delivery and
condensed schedule. Brief outlook at assignments, projects and exams.
Main questions that we ask in this course.
Some graph classes. Planar graphs. Interval graphs. Partial k-trees. Graph assumptions:
simple, connected, undirected, big enough, stored with incidence lists.
Brief example of dynamic programming in a path.
Four tools to solve problems in planar graphs that we will see.
Lots of definitions. Planar drawing. Faces. Closure properties.
Rotation system. Facial circuits. Planar embedding.
Given a rotation system, any face could be the outer-face.
Planar embeddings are not unique.
Example for using the embedding: Menger problem. Right-hand search.
Solving the Menger problem in planar st-graphs. Why this finds the maximum
set of paths.
Thursday, May 14, 2020 (Lecture 2): Solving problems in planar graphs
Dual graphs. Definition and
properties. Dual graphs are not well-defined if graph is not connected.
How to compute and store it. Solving a problem by going over to the
dual graph. Token example: Turning a triangular mesh into a
quadrangular mesh.
Euler's formula. Proof. Lots of consequences. Edge-formulas.
Vertex of degree at most 5.
K5 and K3,3 are not planar.
Algorithmic consequences. Sparsity means algorithms are faster and/or simpler
(e.g. Dijkstra). Min-degree order. 6-coloring. Brief glimpse at 4-color
theorem, no proof. Answering adjacency queries in constant time. Finding
maximum clique.
Week 2
Tuesday, May 19, 2020 (Lecture 3): NP-hardness. Maximum Flow
Proving problems NP-hard in planar graphs. Method 1: crossing gadget.
Example: 3-coloring. The crossing gadget and its colorings.
The reduction.
The graph of a 3SAT problem. Planar3SAT. This is NP-hard (no proof details).
Method 2: planarity-preserving reductions. Independent
Set. Reducing 3-SAT to Independent Set. Observe: this preserves planarity.
Maximum-flow problem. (s,t)-cuts and their values. The MaxFlowMinCut theorem.
No proof of `hard' direction.
Maximum flow in st-planar graphs.
(s,t)-cuts become cycles in dual graph. Rephrase as shortest
path. Proof of correctness by creating a flow.
Thursday, May 21, 2020 (Lecture 4): Planarity testing. Triangulated graphs
How to prove a graph non-planar? Cuts in planar graphs. Bush forms.
Goal: Expand bush forms while maintaining all valid embeddings.
Haeupler-Tarjan do this with DFS. Crucial lemma reformulated (and
strengthened) using descendants. How to store embeddings?
PQ-trees store subsets of permutations. P-nodes, Q-nodes.
PQ-tree reduction: Can we make a given set of leaves consecutive? Sketch of
how to check this in time proportional to set-size.
Haeupler-Tarjan data structures. Store partial bush forms so that
space is linear. How to update when retreating from a node.
Second example of updating. Unsuccessful, so graph is not planar.
Planarity test takes linear time.
Maximal planar graphs. Triangulated graphs. Equivalence.
Triangulated graphs have 3n-6 edges, 2n-4 faces, and are
3-connected. Corollary: Can make a graph triangulated by adding edges.
This can be done in linear time (no details).
Week 3
Tuesday, May 26, 2020 (Lecture 5): Canonical ordering and uses
The canonical order. Definition and properties.
Thm: Every triangulated graph has a canonical order. Proof.
Use canonical ordering to split into forests. How to label the
edges. We obtain three rooted trees (also known as Schnyder wood.)
Canonical orderings and graph drawings.
Every planar graph has a visibility representation.
Invariants to maintain while adding vertices. How to add a vertex.
Corollary: every planar graph is a grid-minor.
Every planar graph has a planar straight-line drawing.
Invariants to maintain while adding vertices. How to add a vertex.
Coordinates can be made polynomial and even linear (no details).
Thursday, May 28, 2020 (Lecture 6): Friends of planar graphs
Superclasses of planar graphs. Graphs embedded in 3D without crossings.
Graphs of higher genus. H-minor free graphs. Near-planar graphs, in particular 1-planar graphs.
Subclasses of planar graphs.
Outer-planar graphs. Characterization and linear-time recognition.
Maximal outer-planar graphs. Properties. Inner dual. Vertex ordering.
k-outer planar graphs. Onion peels and outerplanarity.
Relationship to height of planar grid-drawings.
2-terminal series-parallel graphs. The SP-tree.
Properties of 2-terminal SP-graphs.
Not all outerplanar graphs are 2-terminal SP-graphs, e.g. K1,3.
SP-graphs.
Apollonian networks. Vertex ordering where
everyone has exactly three predecessors.
Hierarchy among all these graph classes. End of Part I of the course.
Week 4
Tuesday, June 02, 2020 (Lecture 7): Interval graphs and chordal graphs Interval graphs. Definition. Properties and graphs that are not
interval graphs. Chordal graphs. All trees are chordal. Graphs
with a PEO. These are chordal. All chordal graphs have PEO,
but no proof of this yet.
Algorithms. Greedy-coloring gives optimum coloring and maximum clique.
Greedy-algorithm for independent set on reverse PEO gives optimum.
Dominating set is NP-had on chordal graphs.
Friends of interval graphs. All graphs are intersection graphs.
Geometric intersection graphs. H-free graphs. Perfect graphs.
Finding a PEO. Simple approach: repeatedly remove simplicial vertex.
Faster approach: MCS. Proof that for a chordal graph this gives a PEO.
Thursday, June 04, 2020 (Lecture 8): Recognizing interval graphs. Tree decompositions
Testing whether a vertex order is a PEO. This can be done in
linear time. So can recognize chordal graphs in linear time.
Interval graph recognition. Characterization of an interval graph
via consecutive order of maximal cliques.
How to find maximal cliques in chordal graphs.
Testing existence of consecutive maximal-clique-order with PQ-trees.
With that, can recognize interval graphs in linear time.
Consecutive maximal-clique-order gives strong path
decomposition.
Generalize to chordal graphs. Strong tree decomposition.
From strong tree decomposition to PEO: Enumerate vertices according to
pre-order of the bags. From PEO to strong tree decomposition:
add one bag at a time containing {vi} cup Pred(vi). So maximum
clique-size relates to bag-size.
Week 5
Tuesday, June 09, 2020 (Lecture 9): Partial k-trees and treewidth
Three equivalent statement about trees. Now generalize to k-trees.
Equivalent characterization. Number of edges.
Some 1-trees, 2-trees, 3-trees that we have seen. Maximal outerplanar,
Apollonian networks. 2-terminal SP-graphs?
Partial k-trees. Some examples we have seen.
Chordal graphs with small cliques are partial k-trees.
Weak tree decompositiion. We care about how small bags are.
Treewidth of a graph.
A few more properties of partial k-trees.
How to lower-bound treewidth. The treewidth of a grid.
Thursday, June 11, 2020 (Lecture 10): SP-graphs. Branchwidth.
Series-parallel graphs revisited. They are the same as
the partial 2-trees. Any minor has a multiple edge or a deg-2 vertex.
This implies algorithm to recognize SP-graphs.
Branch decomposition and separators on links.
Branchwidth of SP-graphs and grids. Closure under minors.
Branchwidth and treewidth are asymptotically the same. Proof.
Branchwidth in planar graphs. Can compute it in quadratic time (no details).
If planar graph has spanning tree of small height then it also has small
branchwidth (hence treewidth).
Week 6
Tuesday, June 16, 2020 (Lecture 11): Pathwidth, cutwidth and friends
Path decompositions and pathwidth. Properties. Relationship to interval graphs.
Pathwidth of trees. Main paths. k-caterpillars.
Cutwidth, vertex-separation number, and some simple properties.
The vertex-separation number equals the pathwidth. Proof.
Similar: The cutwidth is closely related to the pathwidth of the line graph. No proof.
Weighted cutwidth is strongly NP-hard, even on trees. Proof of weak NP-hardness.
Reduction to unweighted cutwidth in SP-graphs. Sketch of reducing max-degree.
Hence Pathwidth is NP-hard even in planar graphs.
Brief outlook at other width-parameters. End of Part II of the course.
Thursday, June 18, 2020 (Lecture 12): Trees and dynamic programming
Weighted independent set in trees. Greedy doesn't work. Top-down
recursive approach by restriction solution-types.
This evaluates subtrees repeatedly;
to save run-time turn it into bottom-up dynamic program.
Defining alpha(v,.). Recursive formulas. Code and run-time.
Doing it again for matching, and then for dominating set.
Main idea of DP in graphs with small separators.
Independent set in 2-terminal SP-graphs via dynamic programming
bottom-up in the SP-tree. Function, formulas, code.
Week 7
Tuesday, June 23, 2020 (Lecture 13): Dynamic programming in partial k-trees
DP in graphs of pathwidth 3. Step 1:
Find a nice path decomposition. Forget-nodes and introduce-nodes.
Step 2: Define subgraphs in which we'll search for solutions.
Step 3: Define function to be optimized.
Step 4: Develop recursive formulas.
Pseudo-code. Note that this works for any constant pathwidth,
with very little change.
Dynamic programming in partial k-trees.
Step 1: Find a nice tree decomposition.
Step 2: Define subgraphs. Step 3: Define functions. Step 4: Find
formulas (most of them inherited from pathwidth). The concept
of fixed-parameter tractability.
Thursday, June 25, 2020 (Lecture 14): MSOL. k-outer-planar graphs
Monadic second-order logic (MSOL): express a graph property as a logic
formula. What is allowed/not allowed. Lots of examples, culminating
in how to express `has Hamiltonian cycle' in MSOL2.
Courcelle's theorem. Brief hints at other methods.
Recall k-outer planar graph. Some properties of edges.
Any k-outerplanar graph is a partial 3k-tree. Proof, via a detour:
we can add edges to a k-outerplanar graph so that the result is planar
and has a spanning tree of height at most k.
Can make graph outer-planar by removing
half the vertices. Similar approach with a twist
gives a 1/2-approximation for independent set in planar graphs.
Baker's approximation scheme. Can make graph k-outer-planar by removing
few vertices. Doing it again, with a twist, gives (k/k+1)-approximation
for independent set in planar graphs.
Week 8
Tuesday, June 30, 2020 (Lecture 15): Balanced separators
(Weighted) alpha-separators. Some observations/conventions. Separators in grids.
Some examples that do not have small alpha-separators.
Every tree has 1/2-separator of size 1. Implication for pathwidth of trees.
Every partial k-trees has a 1/2-separator of size k+1. Not true for size k.
The planar separator theorem: Every planar graph has a
1/2-separator of size O(sqrt{n}).
Separator hierarchies. Applications for pathwidth-bounds for planar graphs and partial k-trees.
Thursday, July 02, 2020 (Lecture 16): Applications of separators
Divide-and-conquer algorithms, e.g. for shortest cycles, minimum cut and maximum matching.
Using separator hierarchies for approximating independent set.
Towards approximating treewidth. Separators vs. separations. How to find
W-separations.
W-separators imply tree decompositions. Proof.
Putting it all together gives a 4-approximation algorithm for the treewidth
that is fixed-parameter tractable in the treewidth.
Week 9
Tuesday, July 07, 2020 (Lecture 17): Grid minors. Bidimensionality
For planar graphs, have faster approximation algorithms for treewidth.
Always either have a big grid as a minor or small treewidth. Proof.
In consequence, it is FPT to test whether a planar graph G contains a
planar graph H as a minor. Same result holds for non-planar G (no proof).
Exploiting dichotomies. Example: Longest path. Either DFS-tree has large
height (then have a long path) or pathwidth is small (then solve via DP).
Improving the run-time. Either have a large grid-minor
(then have a long path), or have small treewidth (then solve via DP).
Run-time is FPT, but `only' in sqrt{ell}.
Towards Graph Minor Theorem. H-free graphs. If graph class is closed,
then it can be characterized by forbidden subgraphs.
Thursday, July 09, 2020 (Lecture 18): WQO and Graph Minor Theorem
Minor-posets of a graph class. Infinite anti-chains. If we can
prove that there are no infinite anti-chains then GM Theorem holds. Proof.
Sink-sequences. The concept of WQO. If we show that any graph class is
WQO then GM Theorem holds Proof. Stars are WQO. In consequence, can
extract infinite minor-chain.
Expanding WQO classes. Can put two components together. Can put k
components together. Can put any finite number of components together. Proof.
Kruskal's theorem: Forests are WQO. Proof with some details omitted.
Similar: partial k-trees are WQO. Planar graphs are WQO. Briefest of
sketch how to extend to higher genus. So GM Theorem holds. Implications.
Any minor-closed graph class can be recognized in polynomial time.
What to remember after the final.
