All about Planar Graphs

COSC 149.12, Spring 2026

Main | Schedule | Homeworks | About

Course Schedule

Basics

Mar 30

why are we here, overview; Euler formula

• Proofs and Refutations, Imre Lakatos. We have not formally proven Euler's formula today. But what constitutes a proof?

Apr 01
[scribble]

rotation system, duality, tree-cotree decomposition, Euler characteristic

• Erickson Chap 2.1-2.2, 2.6-2.7
• 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

Apr 06
[scribble]
[slides]

surface, curvature, discrete Gauss-Bonnet; Cauchy rigidity theorem

• 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.
• 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.

Apr 08
[scribble]

medial and radial graphs, quadrangulations; discrete metric, homotopy and electrical moves, Steinitz theorem

• Erickson Chap 6.5 talks about medial and radial construction (and other derived maps). It's hard to find a good modern reference.
• 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.

Apr 13
[scribble]

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.
• Generalization of Schnyder woods to orientable surfaces and applica tions by Benjamin Lévêque generalizes Schnyder woods to surfaces

Topological Graph Theory

Apr 15

Lipton-Tarjan path separator, cycle separator

• Erickson 14.1-14.4

Apr 20

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

• lecture 7: Minors in Planar Graphs by Michał Pilipczuk

Apr 22

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

• Separator Theorems, blog post by Hung Le: good introduction to separatos on minor-free graphs A Separator Theorem for Graphs with an Excluded Minor and its Applications, the original AST paper

Physical and Riemannian Representations

Apr 27

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

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.

Apr 29

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

May 04

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.

Graph Drawing and Algebraic Representations

May 06

crossing lemma, point-line incidency; beyond planarity, k-planar and k-quasi-planar graphs

• Geometric Graphs: The Crossing Lemma and Two Applications by William Steiger
• Sum-Product Problem by Yufei Zhao. This lecture notes talks about the crossing lemma and a surprising application in additive combinatorics.
• Graphs drawn with few crossings per edge by János Pach and Géza Tóth, original paper on k-planar graphs
• Generalizations of the Crossing Lemma by Géza Tóth

May 11

weak and strong Hanani-Tutte theorems, poly-time LP planarity testing

• Hanani–Tutte and Related Results by Marcus Schaefer: survey of Hanani-Tutte theorems Removing even crossings by Pelsmajer-Schaefer-Štefankovič, a proof of strong Hanani-Tutte without Kuratowski's theorem

Geometric Intersection Graphs

May 13

pseudodisks, planar support, union complexity

May 18

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

May 20

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

May 25

[No class today]

Misc.

May 27

Baker's technique, treewidth-diameter property, contraction decomposition, bidimensionality; grid-tree, cop-decomposition, strong product theorem

Jun 01

quasi-isometry of string graphs into planar graphs

Topics we might not get to cover

orthogonal representation: Colin de Verdiere invariant, SDP, max-cut

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

low-diameter decompositions: padded decomposition, Klein-Plotkin-Rao iterative layered decomposition

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

graph drawing: clustered planarity, upward planarity

planarity testing: SPQR and PC trees

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