All about Planar Graphs

COSC 149.12, Fall 2024

Main | Schedule | Homeworks | About

Course Schedule

Basics

9/17

why are we here, overview; Euler formula, crossing lemma

• Proofs and Refutations, Imre Lakatos. We have not formally proven Euler's formula today. But what constitutes a proof?
• The sum-product problem, Yufei Zhao. This lecture notes talks about the crossing lemma and a surprising application in additive combinatorics.

9/19

rotation system, duality, tree-cotree decomposition; Lipton-Tarjan path separator, cycle separator

• Erickson Chap 2.1-2.2, 2.6-2.7
• Erickson 14.1-14.4
• A combinatorial representation for oriented polyhedral surfaces, JR Edmond, 1960. This is Edmond's MA thesis, in which the notion of rotation system first came up.

Combinatorial Representations

9/24

medial and radial graphs, discrete Gauss-Bonnet, electrical moves; Steinitz theorem, Cauchy rigidity theorem

• Erickson Chap 6.5 talks about medial and radial construction (and other derived maps). It's hard to find a good modern reference.
• Transforming Curves on Surfaces Redux by Jeff Erickson and Kim Whittlesey includes a proof to the combinatorial Gauss-Bonnet theorem. Section 4.3 of the lecture notes by Lazarus and de Mesmay deals with the case when the (discrete) surface has holes.
• My thesis! Lemma 2.1 provided a proof to the bigon reduction. You can find a few reference from the paragraph, including Gilmer-Litherland which is also relevant to the lattice theorem in the next lecture.
• Proofs from THE BOOK by Aigner and Ziegler has a chapter on Cauchy rigidity theorem; but it is missing the crucial part of the proof that there is a vertex where signs changes less than 4 times around it. Eric Demaine's proof is fine, but not enough intuition for me. His book on Geometric Folding Algorithms with Joseph O'Rourke is pretty though.

9/26

Schnyder woods, canonical ordering, barycentric coordinates and grid embedding; α-oritentations and their distributive lattice structure

• Erickson note 11, 2023
• Canonical Orders and Schnyder Realizers by Stephen Kobourov talks about equivalence to canonical / shelling order
• Lattice Structures from Planar Graphs by Felsner, 2004. This paper proofs that α-orientations form a distributive lattice in plane graphs.

Physical Representations

10/1

Tutte drawing, Laplacian, energy minimization; Tutte's spring embedding theorem, Whitney uniqueness theorem

• Erickson note 12, 2023
• Graphs and Geometry by Laszlo Lovasz, Chapter 3.1, 3.2.1

10/3

tensegrity framework and stresses, reciprocal diagrams, polyhedral lifts, Cremona-Maxwell equivalence; weighted Delaunay graph and power diagram

• Erickson note 12a, 2023
• Graphs and Geometry by Laszlo Lovasz, Chapter 3.2.2
• Don Sheehy notes, Fall 2014.

Riemannian Representations

10/8

Koebe-Andreev-Thurston disk-packing, simultaneous orthogonal drawings, cycle separator from disk packing

• On Primal-Dual Circle Representations, Felsner and Rote, SOSA 2019
• Geometric Representations of Graphs, Laszlo Lovasz, Chapter 6.1. This is a draft of the book below, but with the topological argument for existence of radii, instead of the current analytic one, or the algorithmic one from Felsner-Rote.
• Graphs and Geometry by Laszlo Lovasz, Chapter 5.1-5.2

10/10

Cheeger inequality, 2nd eigenvalue of Planar Graphs through disk packing; spectral cuts

• Erickson note 12a, 2023
• Graphs and Geometry by Laszlo Lovasz, Chapter 5.3-5.5
• Har-Peled note 16, 2022.An easy way to get separator from circle packing.
• koebepy by John C. Bowers. Circle packing app on Jupyter notebook.
• Spectral partitioning works: Planar graphs and finite element meshes by Spielman and Teng, 2007 The original proof that second eigenvalue of planar graph is small. See also the lecture notes by Spielman.
• Algorithmic proof of the Cheeger inequality by la Svensson.
• Ken Stephenson webpage. The OG circle packing guy, with this AMS article.

Topological Graph Theory

10/15

graph minors, Kuratowski-Wagner theorem, treewidth, planar grid-minor theorem; non-surface feature, RS structure theorem

10/17

minor-free graphs are like planar graphs: Alon-Seymour-Thomas separator, sparsity bound

Geometric Intersection Graphs

10/22

weak and strong Hanani-Tutte theorems, poly-time LP planarity testing; pseudodisks, planar support

10/24

union complexity, complexity of low-ply system through sampling; clique-based separators, geodesic disks in polygons

Distance Structures

10/29

shortest-path separator, ε-covers, distance oracle; low-diameter and padded decomposition, Klein-Plotkin-Rao iterative layered decomposition

10/31

[No class today]

Sparse Graphs

11/5

Sperner's lemma, strong product theorem, bounded queue number

11/7

coloring, degeneracy, arboricity, sparsity; shallow minors, bounded expansion, polynomial expansion and small separator

Misc.

11/12

Baker's layering, treewidth-diameter property, contraction decomposition, bidimensionality; grid-tree, cop-decomposition, tree covers

11/14

Monge property, VC-dimesion of geometric objects, distance VC-dimension

11/19

beyond planarity: k-planar, k-quasi-planar; string graphs, separator via L1-embedding

Topics we might not get to cover

orthogonal representations: Colin de Verdiere invariant, SDP

low-distortion routing: multi-commodity flows, L1 embeddings, planar embedding conjecture

topology of graphs: planar covers and Negami 1-2-infinity conjecture, theory of almost-planar graphs

linkage and folding: universality linkage theorem Alexandrov's theorem

planar graph algorithms: disjoint paths, multi-terminal flows and cuts, diameter, matchings, distance oracles

graph drawing: clustered planarity, upward planarity

planarity testing: SPQR tree

new tools: twin-width