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).
Week 3
Monday, May 20, 2024 (Lecture 7): (IMPORTANT! Lecture on May 21 instead!)
Friends of planar graphs
Superclasses of planar graphs. Graphs embedded in 3D without crossings.
That's all graphs (sketch of a proof). Graphs embedded in surface of
higher genus. Rotational system, faces, dual graph all
transfer. Graphs with small crossing number. Graphs with small
local crossing number (also known as k-planar graphs). No details on any of these.
Subclasses of planar graphs.
Outer-planar graphs. Characterization: outer-planar if and only if still
planar when adding a universal vertex. In consequence, can test outer-planarity
in linear time. Maximal outer-planar graphs. These are a triangulated disk,
so have canonical ordering. In fact, every vertex vi (for i≥3)
must have exactly two incoming edges, otherwise not all vertices are on
the outer face. Therefore we have 2n-3 edges, n-3 inner edges, n-1 faces and
n-2 inner faces. So the dual graph is a tree after deleting the outer-face vertex.
k-outer planar graphs. Onion peels. Outerplanarity can be Theta(n).
2-terminal series-parallel graphs. The SP-tree.
Properties of 2-terminal SP-graphs: planar, at most 2n-3 edges, 3-colorable.
Not all outerplanar graphs are 2-terminal series-parallel graphs, e.g. K1,3.
Problem: not closed under taking subgraphs. SP-graphs.
Apollonian networks. Vertex ordering where
everyone has exactly three predecessors and those form a clique
(this will be important later!).
Hierarchy among all these graph classes. End of Part I of the
course.
Wednesday, May 22, 2024 (Lecture 8): Interval graphs and chordal graphs
Interval graphs. Definition.
Every cycle of length >=4 has a chord.
Interval graphs are closed under taking induced subgraphs.
Chordal graphs. Not all
chordal graphs are interval graphs. Example of a tree.
Interval graphs have naturally a vertex order (sorted by left endpoint).
Perfect elimination orders. Not all graphs that have a PEO are
interval graphs (same example). Every graph with a PEO is chordal.
Reverse holds, but not proved yet.
Algorithms. Greedy-coloring gives optimum. Proof. chi(G)=omega(G),
so this also solves Clique. A similar approach works for
IndependentSet and CliqueCover (no details).
Dominating set remains NP-hard in chordal graphs. Reduction from
VertexCover. Any vertex cover in G is also a dominating set in G'.
Any dominating set in G' is (after modifying it to use no edge-nodes)
a vertex cover in G.
Friday, May 24, 2024 (Lecture 9): Friends. Recognizing chordal graphs
Friends of interval graphs. Other interesting classes of intersection
graphs: boxicity-d graphs, (unit) disks graphs.
Other classes of H-free graphs, in particular cographs.
Other classes where omega(G)=chi(G), in particular perfect graphs. No
details on any of these.
Finding a PEO. Simple approach: repeatedly remove simplicial vertex.
Faster approach: Maximum cardinality search. The algorithm. Example.
This can be implemented in linear time by using a sorted doubly-linked
list of non-empty vertex sets. Sketch of how to update in constant time.
Theorem: If G is chordal then MCS gives a PEO. Prove something stronger
by induction: For any component of the rest-graph, the neighbours among the
chosen vertices are clique. Induction step. If condition is violated
then we can find an induced cycle of length at least 4.
Week 4
Monday, May 27, 2024 (Lecture 10): Recognizing interval graphs
How to test whether a vertex order is a PEO. Main insight: Pred(vi) is
subset of vh cup Pred(vh) for last predecessor vh of vi. Second idea: batch
adjacency-testing together and do it via subset-testing in linear time.
In consequence, can recognize chordal graphs in linear time.
Interval graph recognition. G is an interval graph if and only if we
can arrange maximal cliques such that cliques containing a vertex are
consecutive. Proof. Finding all maximal cliques in chordal graphs (no details).
To test for a suitable ordering of maximal cliques, need a new data structure.
PQ-trees. P-nodes, Q-nodes, permitted changes, permissible leaf orders.
Main operation: reduce(I) changes tree to store only permutations where
leaves of I are consecutive. Some
ideas that this can be checked with finite set of rules, applied at each
node of PQ-tree. No details about fast implementation.
With this, interval graph recognition takes linear time.
Wednesday, May 29, 2024 (Lecture 11): Tree decompositions and k-trees
Definition of strong path decompositions. G is an interval graph if and only if it has a strong
path decomposition.
Now generalize to chordal graphs. Strong tree decomposition.
Every graph with a PEO has a strong tree decomposition. From PEO to decomposition:
add one bag at a time containing vn cup Pred(vn). Observe: bag-size is at most omega(G)+1.
From decomposition to PEO: Enumerate vertices according to pre-order of the bags.
Why this gives a PEO. Observe: all cliques are in a bag, so bag-size is exactly omega(G)+1.
Study a subclass of chordal graphs. Recall, trees are chordal. Three
equivalent statement about trees. Now generalize. k-tree definition and
equivalent characterizations.
Examples of k-trees. Trees are 1-trees. Apollonian networks are 3-trees,
but not vice versa. Maximal outerplanar graphs
are 2-trees, but not vice versa.
Friday, May 31, 2024 (Lecture 12): Partial k-trees and treewidth.
Every 2-tree is a 2-terminal SP-graph. Proof via building an SP-tree.
Therefore every partial 2-tree is an SP-graph.
Partial k-trees and lots of results about them. Along the way:
weak tree decompositiion, width of a tree decomposition, treewidth of a
graph. Put together: Any partial k-tree has treewidth at most k.
Also, any 2-terminal SP-graph has treewidth at most 2 (read the tree
decomposition from the SP-tree).
Reverse direction: Every graph of treewidth at most k is a partial k-tree.
Only difficult step: Every chordal graph of clique-size k+1 is a subgraph
of a k-tree. Proof. So from now on `partial k-tree' and `treewidth at
most k' are synonyms. In particular SP-graphs are the same as partial 2-trees.
Some other properties of partial k-trees. Closed under taking subgraphs.
Closed under edge contraction. Closed under taking minors. The axb-grid
has treewidth at most min{a,b}. Proof (mostly by example): can find a
supergraph that is a min{a,b}-tree. The treewidth-bound is tight (no
proof yet).
Week 5
Monday, June 03, 2024 (Lecture 13): Series-parallel graphs
Graphs that do not have small treewidth. Cliques. Treewidth is
closed under taking minors.
The axb-grid has treewidth min{a,b}. (Lower bound not part of course material.)
Treewidth and separators. Every bag defines a separator: connected subgraphs
of G-Xi are in one component of T-i.
Some complexity results without proofs. Computing treewidth is NP-hard.
For fixed k, testing whether tw(G)≤k can be done in linear time (but
very large constant relative to k).
Series-parallel graphs revisited. Equivalences; in particular no K4 minor
and every minor has a vertex with at most 2 distinct neighbours. Proof with a detour:
every 3-connected graph contains a K4-minor.
Last condition gives algorithm to recognize SP-graphs: either find a minor that
violates condition, or get a tree decomposition of width 2. Setting up the bucket
structure (and list R). Doing one round: (a) delete vertex of degree 1, or (b)
delete vertex with degree 2 and distinct neighbours, or (c) delete a parallel edge, or
(d) add a vertex to R, or (e) conclude not an SP-graph. This works as long as we
ensure that R is correct at all times (by removing vertices from it when its neighbours
are changed). We need at most 3m-|R| rounds, hence linear time.
Wednesday, June 05, 2024 (Lecture 14): Friends of treewidth. Branchwidth
There are lots of other width-parameters of a graph. Brief sketch of
cutwidth and bandwidth. axb-grid has bandwidth min{a,b}.
Path decompositions and pathwidth. Equivalent: subgraphs of interval graphs
with small chromatic number (proof was done earlier, via strong path decompositions
of interval graphs). There is a similar equivalence for bandwidth
(using unit interval graphs). No proof.
Study branchwidth in more details because
we will need this to analyze treewidth of some planar graphs.
Recursive edge partitioning. Branch decomposition and separators on
arcs. Branchwidth definition.
Branchwidth is asymptotically the same as treewidth.
Lemma: treewidth + 1 <= 3/2 branchwidth. Proof, by
turning any branch decomposition into a tree decomposition
by letting bags at interior nodes be union of incident seprators.
Lemma: branchwidth(G) ≤ treewidth(G)+1. Proof by
modifying a tree decomposition until it is a branch decomposition.
Detour (will be needed later):
Any spanning tree in planar G gives a spanning tree in dual
by taking the duals of the non-tree edges.
Friday, June 07, 2024 (Lecture 15): Branchwidth in planar graphs. DP in trees
Branchwidth warmup: Every SP-tree can be viewed as branch decomposition of width 2.
Note: separators correspond to nooses. Thm: We can always assume this for
planar graphs. No proof. (Related to this: we can also compute branchwidth
in polynomial time. Likewise no proof.) In consequence, a planar
graph and its dual have the same branchwidth.
Branchwidth in triangulated planar graphs of small radius.
Pf: Use co-tree in
dual graph as host tree for branch decomposition, plus some modifications.
Separators correspond to fundamental cycles in spanning tree, hence
length bounded in terms of radius.
Independent set in trees. The definition of alpha(v,Z) (where Z indicates
whether v is/isn't/maybe) in IS. Recursive
formulas for alpha. The resulting pseudocode will be nearly the same
for all future problems. Linear run-time as long as formulas can be evaluated
in O(deg(v)) time.
Week 6
Monday, June 10, 2024 (Lecture 16): Dynamic programming in partial k-trees
Dominating set in trees. The definition of delta(v,Z) (where Z indicates
whether v is/isn't/maybe) in DS. Recursive formulas. A few new ideas:
(1) If the formula depends on one child, then compute it for each child
and take the best solution. (2) Sometimes we have to define more functions
so that we can get recursive formulas. Then we need recursive formulas for
those, so this can repeat. (3) The base case is not always automatically
covered; sometimes need to set to +infty or -infty to indicate `impossible'.
Now: dynamic programming in graphs of pathwidth 3. Step 1:
Find a nice path decomposition. Forget-nodes and introduce-nodes. Sketch
of why this exists.
Step 2: Define subgraphs in which we'll search for solutions by combining
all bags to the left.
Step 3: Define function to be optimized. (Here again independent
set.) Step 4: Develop recursive formulas. The formula for a
leaf-node. The formula for a forget-node. The formula for
an introduce-node. Sketch of pseudo-code. Run-time.
Dynamic programming in partial k-trees.
Step 1: Find a nice tree decomposition. Definition, and sketch
why it always exists. Step 2: Define subgraphs by combining all bags
at descendants. Step 3: Function exactly as for pathwidth.
Step 4: Recursive formulas exactly as for pathwidth, except at
a join node.
This gives an algorithm that's exponential in k, but polynomial in n.
Wednesday, June 12, 2024 (Lecture 17): Problems in partial k-trees.
DP summary. This works for many other problems (not always with the
same run-time).
The concept of fixed-parameter tractability (FPT). Hints at other results
about FPT; no details.
What other problems can be solved on partial k-trees. Courcelle's theorem:
If a graph property can be expressed in MSOL2,
then testing it is FPT in the treewidth. (No proof.) MSOL:
express a graph property as a logic formula in monadic second-order logic.
What is allowed/not allowed. Lots of examples. G has a triangle.
G has min-degree 2. G is 2-regular. G is connected. But we can't
quantify over a subgraph of G.
An extension: MSOL2, also allow subsets of edges and restricting
adjacency-queries to such. G has a Hamiltonian cycle can be
expressed in MSOL2. In this course, we will not distinguish
carefully between MSOL and MSOL2.
A few more non-trivial examples. The H-minor problem. Equivalent
reformulation can easily be expressed in MSOL, so this is FPT in the
treewidth. (We will later see that it is actually polynomial in general.)
The LongestCycle problem. NP-hard in general, polynomial for constant length
of cycle, FPT in the treewidth since we can express it in extended MSOL2
(i.e., permit optimization over weights on quantified sets).
Not everything is FPT in the treewidth. Example cutwidth. Polynomial in
trees, but NP-hard in a weighted version which (with lots of omitted detours)
means it is NP-hard in SP-graphs. Why DP fails for the cutwidth problem.
Friday, June 14, 2024 (Lecture 18): Baker's PTAS for planar graphs
Brief review of approximation algorithms. Known: No c-approximation
algorithm for independent set for constant c. But: can do better in
planar graphs.
Recall k-outer planar graph. Onion peels.
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. Then use previous results.
Every planar graph can be made outerplanar by deleting at most n/2 vertices.
Proof. Could even do a weighted version. This leads to a 1/2-approximation
for IS: Consider the two ways to make the graph outer-planar by deleting a
vertex set, find best IS in each of the two graphs and return the better one.
Why this is a 1/2-approximation.
Now everything once more, but for k-outerplanar graphs.
Every planar graph can be made
k-outerplanar by deleting at most n/(k+1) vertices. Consider the
(k+1) ways of making a graph k-outerplanar, by removing one of k+1
vertex sets. Find best IS in each of those and return best one.
Why this is a (1-1/(k+1))-approximation.
Week 7
Monday, June 17, 2024 (Lecture 19): Separator theorems
Polynomial-time approximation schemes (PTAS). Baker's theorem: Have
a PTAS for independent set in planar graphs.
Separators and where we already saw them (cutting sets, bags of tree
decomposition, arcs of branch decomposition, the removal-sets for
Baker's PTAS). Now new goal: make flaps a fraction smaller.
alpha-separator definition.
Theorem: Every tree has a 1/2-separator of size 1.
Proof via algorithm to find the vertex.
An axb-grid has a 1/2-separator of size min{a,b}. Proof. It does not have a 1/2-separator
of size min{a,b}/2. Proof.
Theorem: Every partial k-trees has a weighted 1/2-separator of size k+1.
Proof by applying the tree-separator-theorem to a (suitably modified) tree
decomposition. Some partial 2-trees do not have 1/2-separators of size 2.
The planar separator theorem: Every planar graph has a weighted
1/2-separator of size O(sqrt{n}). Proof via making graph O(sqrt{n})-outerplanar
by removing O(sqrt{n}) many vertices.
Wednesday, June 19, 2024 (Lecture 20): Separators: applications and extensions
Application: Divide and conquer algorithms. Example: Maximum matching.
Example: Matrix manipulations.
Separator hierarchies. These naturally give rise to a path decomposition.
Why this is a path decomposition, what is its width? Consequences:
Trees have pathwidth O(log n). k-trees have pathwidth O(k log n).
Planar graphs have pathwidth O(sqrt{n}) since the contributions of smaller
components ``disappear'' in a geometric series.
All these could also have been proved directly by induction, but the
following could not. Generalized separator theorem:
Planar graph have epsilon-separator for any epsilon (not necessarily constant)
of size O(sqrt{n/epsilon}). Proofidea: build separator hierarchy until the
leaves have weight epsilon*w(V). Separator is then everyone that is not in
a leaf; the main difficulty is in arguing that the size-bound holds. (No details.)
Application: Another PTAS for independent set, and shortest paths. (No details
on either.)
Friday, June 21, 2024 (Lecture 21): Treewidth and separators
Had: Small treewidth implies small separators. Now reverse direction:
If G and all induced subgraphs have small 1/2-separators, then G has
small treewidth. Proof, with the main idea to fix a vertex set W that
must be in a bag and using a separator w.r.t. weight-function chiW.
Same proof would work for other alpha-separators, with a suitable choice of
size for W. Use this for an approximation algorithm for treewidth. Detour:
separators vs. separations. Every alpha-separator also implies a separation
with balance max{alpha,2/3}. Proof.
Algorithm to test existence of an alpha-separation for weight-function chiW.
Guess partition of W, then reduce the problem to a Menger problem to find the
smallest possible separator-set S. Run-time is FPT in |W|.
Approximation algorithm. Try all k until we succeed, and call sub-routine
that either finds a tree decomposition of size O(k), or (correctly) says that
the treewidth is greater than k (with exactly the same proof idea as we had
earlier). Run-time is FPT in the treewidth (and quadratic in n).
Many improvements to approximation factor and run-time possible (no details).
Week 8
Monday, June 24, 2024 (Lecture 22): Treewidth and grid-minors; conclusion
Had: Big grid-minor implies big treewidth. Now reverse direction, at
least for planar graph G: If tw(G) > 5k-5, then G contains a kxk-grid
as a minor (and we can find grid or tree decomp. of small width in polynomial
time). Proof similar to last time: try to build a tree decomp. with vertex
set W in one bag. This time, all of W is on the outer-face. Search for
disjoint paths between pairs of (temporarily added) poles. If there are
few, then G has small 3/4-separator and we can find small tree decomp. If
there are lots, then use the paths to find a grid.
Algorithm has quadratic run-time and is a 5-approximation algorithm for treewidth.
Dichotomy-based algorithms: Graph falls into one of two situations, and
either one can be used to solve the problem easily.
Example: Longest path. Either DFS-tree has large
height (then have a path) or DFS-tree (interpreted as separator
hierarchy) gives path decomposition of small width (then solve via DP).
Better approach: use tw-or-grid algorithm. If treewidth is small then
solve via DP. Otherwise contains large grid, which contains a long path.
Run-time is FPT in output-size ell, but the dependency is subexponential (i.e.,
exponential in sqrt{ell}).
Similar approach: How to test whether a graph H is a minor of a planar graph G.
Can test this (via MSOL) if treewidth is small, and answer is `yes' if treewidth
is big (hence G contains big-enough grid for a visibility representation of H,
hence H is a minor of G).
Generalizations (without proof): Can drop `planarity', i.e., test
whether H is a minor in any graph G in poly-time (if |H| is constant).
Graph Minor Theorem (obviously without proof). Algorithmic implication:
Any minor-closed graph class has a quadratic-time recognition algorithm,
but we don't know what it is and it would not be practical. End of main cs762 material.
Wednesday, June 26, 2024 (Lecture 23): extra topics (planarity testing)
How to argue that a graph is NOT planar? Standard technique would be to exhibit
K5 or K3,3, but this is not what we do here. Instead observe
that for any subset V' of vertices, the graph G[V'] has planar drawing where cut-edges are
on the outer-face. We can even force the cut-edges to one vertex v to be consecutive in
some sense (under some connectivity restrictions). Formal definition of bush form and
what embeddings it must have if G is planar.
Algorithm idea: Run DFS and keep track of suitable embeddings of bush forms throughout.
Classification of vertices as undiscovered, finished and active. Definition of V'(w).
We store all possible leaf-orders of B[V'(w)] for all active vertices w. Data structure
for this: PQ-tree.
Three possible updates that must happen during the DFS. Case 1 (easy): discover new
vertex w. Case 2 (easy): explore along non-tree edge. Case 3 (not easy): vertex w
is now finished. We must merge PQ(v) and PQ(w), but first `clean up'. Call Reduce
operation on all edges from v to descendants in V'(w). If this fails then by lemma
G was not planar. If it succeeds, then update PQ(w) and then merge.
If we finish at root then G is planar. This does NOT give the planar embedding, but
it could be extracted via a more complicated data structure called SPQR-tree (no details).
Run-time: Each step is O(1) or proportional to number of edges removed from PQ-trees, so
O(n) overall. Brief history of planarity testing algorithms.
Friday, June 28, 2024 (Lecture 24): Student presentations (Product Structure Theorem). Computing canonical ordering.
Definition of the strong graph product. Goal of today: Every planar graph G is a subgraph of the strong product
of a path P and a graph H that has small treewidth. We may as well assume that G is triangulated.
Compute BFS-tree with root on the outer-face. Define a vertical path to be a
path between ancestor and descendant in the BFS-tree. Lemma: For any set D of vertical paths in G,
if H := G/E(D) (i.e., contract path in D), then G is a subgraph of the strong product
of H with a suitably long path. Proof.
So goal becomes to pick a set of vertical paths D such that H has small treewidth. Need a detour: Sperner's lemma.
If a triangulated disk has 3 colors assigned to vertices (with some conditions on outerface vertices), then there
exists an interior face that has all 3 colors. No proof.
Now for finding the vertical paths D. Invariant: We find these for a triangulated disk G for which all outerface
vertices are already assigned to one of at most five vertical paths, and inner vertices are not yet assigned. We will
also at the same time find a tree decomposition of G/E(D) of width at most 6 for which the boundary-paths (each contracted
into a vertex) are all in
one bag. Base case of a triangle is trivial.
For the step, assign each interior vertex v to the boundary-path hit first when
going up from v in the BFS-tree. Assign three colors to resulting five vertex-sets in a particular way (no details). Find
Sperner-triangle, and the three vertical paths from its three vertices to the boundary-paths. This naturally splits G
into three non-trivial subgraphs; if we choose the colors suitably then each of them is again bounded by at most 5 vertical paths.
So can find tree decompositions for them by induction, and combine them suitably to get one for G.
Run-time: O(n) recursions. In each, the bottleneck is to find the coloring and Sperner's triangle, which can be
done in linear time. So quadratic run-time (this can be improved, no details).
Complete topic-switch: Computing a canonical ordering in linear time. Reminder of the definition. To find
it, we repeatedly need to find a vertex ≠ a,b on the outer-face that has no chord on the outer-face (and then delete it).
Rephrase `no chord' as `the outer-face degree is exactly 2'. Idea: store all outer-face vertices ≠a,b in a data
structure Q with their outer-face-degree as priority. Using a list-of-sets, we can then find minimum-priority
vertex (which has outer-face-degree 2) in constant time. How to update. First update since we delete a vertex v
(this takes O(deg(v)) time). Then, for each vertex w that is new to the outer-face, update priority of its neighbours
and itself (some details omitted here).
This takes O(deg(w)) time. Since every vertex comes to the outerface only
once and is deleted only once, the total time is linear.
Lots of announcements: Projects, lecture notes, final, assessments.
