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, crossing lemma

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

Apr 01

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

Apr 06

surface, curvature, discrete Gauss-Bonnet; Steinitz theorem, 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

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

• 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

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.

Topological Graph Theory

Apr 15

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

Apr 20

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

Physical Representations

Apr 22

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

Apr 27

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

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.

Algebraic Representations

May 06

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

May 11

Colin de Verdiere invariant, SDP, max-cut

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

VC-dimesion of geometric objects, distance VC-dimension

May 25

[No class today]

Misc.

May 27

Sperner's lemma, strong product theorem, bounded queue number; grid-tree, cop-decomposition

Jun 01

[TBD]

Topics we might not get to cover

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