OneDimensional Computational Topology
For each lecture, I provide links to typeset notes (until I ran out of steam), scribbles ("boardwork"), videos, and other reading/viewing material. (Warning: External links to papers may rot over time.) Lecture topics in (parentheses) were briefly sketched or skipped entirely in the actual lecture, but may still appear in the lecture notes. A complete archive of lecture videos is available on a separate site.
Polygons in the plane
 Tue Aug 25

Simple polygons: Jordan polygon theorem, pointinpolygon algorithm, trapezoidal decompositions, polygon triangulations
[
html notes,
pdf notes,
scribbles,
video,
Eames 1961
]
 Thu Aug 27

Winding numbers: Fast and Loose, nonsimple polygon area, winding number definitions, homotopy, (safe) vertex moves, simplicial approximation, homotopy invariance
[
html notes,
pdf notes,
scribbles,
video,
Brushwood 2009
]
 Tue Sep 1

Homotopy testing: crossing sequences, reduction, uniqueness, homotopy invariance again
[
html notes,
pdf notes,
scribbles,
video
]
 Thu Sep 3

Faster homotopy testing: trapezoidal decomposition, horizontal and vertical ranks, rectification, bracket slides, (layered range trees)
[
html notes,
pdf notes,
scribbles,
video,
Cabello Liu Mantler Snoeyink 2003,
Efrat Kobourov Lubiw 2006
]
 Tue Sep 8

Shortest homotopic paths
[
html notes,
pdf notes,
scribbles,
video,
Leiserson Maley 1985,
Hershberger Snoeyink 1994
]
Planar curves
 Thu Sep 10

Immersions, image graphs, homotopy moves, $n$ vertices implies $n+2$ faces, signed Gauss codes, Gauss diagrams, tracing faces
[
html notes,
pdf notes,
scribbles,
video,
Carter 1991
]
 Tue Sep 15

Winding numbers, Alexander numbering, smoothing, unsigned Gauss code planarity, parity (Gauss, Nagy), treeonion figures, bipartite interlacement (Dehn)
[
html notes,
pdf notes,
scribbles,
video
]
 Wed Sep 16

Jeff's Graph Drawing talk
 Thu Sep 17

Curve contraction: Steinitz's algorithm, rotation number, writhe, defect, (regular homotopy, Whitney–Graustein theorem, strangeness)
[
html notes,
pdf notes,
scribbles,
video,
Nowik 2009,
Chang Erickson 2017
]
 Mon Sep 21
 Paper chase assignment due
Planar maps
 Tue Sep 22

Abstract graphs (darts), topological graphs, data structures, embaddings, maps, rotation systems, duality, derived maps
[
html notes,
pdf notes,
scribbles,
video
]
 Thu Sep 24

Deletion and contraction, treecotree decomposition, Euler's formula, discrete GaussBonnet formula
[
html notes,
pdf notes,
scribbles,
video
]
 Tue Sep 29

Straightline embedding, canonical ordering, Schnyder woods, grid embedding
[
html notes,
pdf notes,
scribbles,
video,
De Fraysseix Pach Pollack 1990,
Schnyder 1990
]
 Thu Oct 1

Equilibrium stresses, Tutte's spring embedding
[
html notes,
pdf notes,
scribbles,
video,
Tutte 1963,
Floater 1997,
Spielman 2018
]
Planar paths, cuts, and flows
 Tue Oct 6

Multiplesource shortest paths
[
html notes,
pdf notes,
scribbles,
video,
Klein 2005,
Chambers Cabello Erickson 2013
]
 Thu Oct 8

Separators and $r$divisions
[
html notes,
pdf notes,
scribbles,
video,
Klein Mozes Sommer 2012,
HarPeled Nayyeri 2018
]
 Tue Oct 13

Faster shortest paths, with and without negative edges
[
html notes,
pdf notes,
scribbles,
video,
Lipton Rose Tarjan 1979,
Fakcharoenphol Rao 2006,
Klein Mozes Weimann 2009
]
 Thu Oct 15

Minimum cuts
[
html notes,
pdf notes,
scribbles,
video,
Reif 1983
]
 Tue Oct 20

FRDijkstra and faster minimum cuts (finished on Thursday)
[
html notes,
pdf notes,
scribbles,
video,
Fakcharoenphol Rao 2006,
Italiano Nussbaum Sankowski WulffNilsen 2011
]
 Thu Oct 22

Maximum flows
[
updated SODA 2011 slides,
video,
Borradaile Klein 2009,
Erickson 2010
]
Surface maps
 Tue Oct 27

Surface maps: 2manifolds, polygonal schemata, cellular embeddings and rotation systems, orientation and genus, band decompositions, reflection systems, deletion and contraction
[
html notes,
pdf notes,
scribbles,
video
]
 Thu Oct 29

Surface classification: KerékjártóRado theorem, treecotree decompositions, systems of loops, handles, twists, Dyck's surface, classification, Euler characteristic, discrete GaussBonnet
[
html notes,
pdf notes,
scribbles,
video,
Gilbert Hutchinson Tarjan 1984,
Sppstein 2003
]
 Fri Oct 30

Project proposals due
 Tue Nov 3

Election day — No lecture
 Thu Nov 5

Overview of submitted project proposals
[
🔒 all proposals,
🔒 video
]
 Tue Nov 10

Homotopy testing (Dehn's algorithm)
[
html notes,
pdf notes,
scribbles,
video,
Lazarus Rivaud 2012,
Erickson Whittlesey 2013
]
 Thu Nov 12

Shortest nontrivial cycles
[
sorry no notes,
scribbles,
video,
Erickson HarPeled 2003,
Cabello Chambers Erickson 2013
]
 Tue Nov 17

Minimum cuts and $\mathbb{Z}_2$homology
[
sorry no notes,
scribbles,
video,
Chambers Erickson Nayyeri 2009,
Erickson Nayyeri 2011
]
 Thu Nov 19

Maximum flows and $\mathbb{R}$homology
[
sorry no notes,
scribbles,
video,
Chambers Erickson Nayyeri 2012
]
 Nov 23–27
 Thanksgiving break — No lectures
Stuff and oddments
 Tue Dec 1

Approximation schemes via lowdiameter slicing: carvings, branchwidth, dynamic programming, radial greedy treecotree decomposition, branchwidth ≤ diameter + 1, slicing
[
sorry no notes,
scribbles,
video,
Baker 1994,
Eppstein 1999,
Demaine Hajiaghayi Mohar 2011
]
 Thu Dec 3

Planarizing and separating surface maps: Menger's theorem, systolic bounds, multicycle separators $O(\sqrt{ng}\log g)$, unstructored separators $O(\sqrt{ng})$
[
sorry no notes,
scribbles,
video;
Colin de Verdière, Hubard, de Mesmay 2014;
Gilbert Hutchinson Tarjan 1984
]
 Tue Dec 8

Chasing puppies: configuration torus, puppy diagram, essential and contractible critical cycles, human diagram, two essential critical cycles, dexter and sinister strategies, chamfering
[
sorry no notes,
scribbles,
video;
Abrahamsen Erickson Kostitsyna Löffler Miltzow Urhausen Vermeulen Viglietta 2020,
Abel Akitaya Demaine Demaine Hesterberg Korman Ku Lynch 2020
]
 Wed Dec 9

Project reports due
 Thu Dec 10

Last day to submit ICES evaluation forms
 Dec 11–18
 🔒 Final project presentations
 Fri Dec 18

Extended drop deadline (11:59pm) [info]
Related topics I didn't have time for
This list is far from exhaustive! Topics in bold are the omissions I regret most.

Polygons:
weakly simple polygons [Meister, Minc, Skopenkov, ...], Fréchet distance [Alt Godau], mountain climbing [Homma, Huneke], linkages and rigidity, Carpenter's rule theorem [Connelly Demaine Rote, Streinu]

Topological combinatorial geometry:
Jordan curve theorem via Hex/Y, pseudoline arrangements, order types [Goodman Pollack], stretchability and universality [Mnëv, Shor, ...], $\exists\mathbb{R}$completeness

Generic curves: selfoverlapping curves, homotopy area

Planar map structures:
Forbidden minors [Kuratowski, Wagner], Maxwell–Cremona correspondence, Steinitz's theorem (TutteMaxwell or via medial curve simplification), Alexandrov's theorem, KoebeAndreevThurston circlepacking, squared rectangles [Dudeney, Dehn, Brooks Tutte, ...], electrical reduction [Kennelly, Steinitz, Feo Provan, Truemper, ...], HananiTutte theorem, OkamuraSeymour theorem, crossing lemmas [Ajtai Chvátal Newborn Szemerédi Leighton], rigidity, pseudotriangulations, the carpenter's rule, string graphs, distributive flow lattices [Khuller Naor Klein], flip graphs

Planar graph algorithms:
enumeration/random sampling [Tutte], planarity testing, morphing [Steinitz Rademacher, Cairns], maximum cut $\leftrightharpoons$ Chinese postman [Hadlock], planar graph isomorphism [Weinberg Hopcroft Tarjan Wong], planar network simplex, spanners, approximate distance oracles, GomoryHu trees, multiterminal maximum flow, subquadratic diameter, weak embeddings, clustered planarity, branchwidth (and other width parameters), approximation via local search [Mattieu], appromimation via brick decomposition [Klein, Demaine, inter alia], contour trees, terrain simplification, homotopy height

Surface map structures:
Discrete differential geometry (an entire course), graph minor theory [Robertson Seymour] (an entire course), toroidal geodesic/periodic planar embeddings, geodesic spring embedding [Colin de Verdière oncle], circle packing [Mohar], shortestpath embeddings, systolic inequalities, holiest paths and flows, toroidal MaxwellCremona [Erickson Lin]

Surface map algorithms:
Canonicalizing systems of loops [Dehn, Brahana], Reeb graphs, mesh simplification, genus approximation [Sidiropoulos et al.], curve tracing [Erickson Nayyeri, Bell], isotopy testing [Colin de Verdière neveu, De Mesmay], shortest homotopic paths [Colin de Verdière neveu, Lazarus, Erickson], optimal cycle bases, optimal homology bases, GomoryHu trees, homotopy area [Chambers Wang], more approximation algorithms (an entire course), persistent homology (an entire course)