OneDimensional Computational Topology
CS 598 JGE, Spring 2023
For each lecture, I provide links to typeset notes (at least until I run out of steam), scribbles ("boardwork"), videos, and other reading/viewing material. (Warning: External links to papers 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. (Lecture videos from 2020 are also available.) The symbol 🆕 indicates lecture notes that were newly written in 2023; these notes are much more likely to be incomplete.
All future lecture topics are subject to change.
Polygons in the plane
 Jan 18

Simple polygons: Jordan polygon theorem, pointinpolygon algorithm, trapezoidal decompositions, polygon triangulations
[
html notes,
pdf notes,
scribbles,
video,
Eames 1961
]
[
2020 scribbles,
2020 video
]
 Jan 20

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
]
[
2020 scribbles,
2020 video
]
 Jan 25

Homotopy testing: crossing sequences, reduction, uniqueness, homotopy invariance again
[
html notes,
pdf notes,
scribbles,
video,
]
[
2020 scribbles,
2020 video
]
 Jan 27

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
]
[
2020 scribbles,
2020 video,
]
 Feb 1

Shortest homotopic paths: triangulation, crossing sequences, reduction, the funnel algorithm, holes for free!
[
html notes,
pdf notes,
scribbles,
video,
Leiserson Maley 1985,
Hershberger Snoeyink 1994
]
[
2020 scribbles,
2020 video
]
Planar curves
 Feb 3

Immersions, image graphs, homotopy moves, Steinitz's contraction algorithm, $n$ vertices implies $n+2$ faces, signed Gauss codes, Gauss diagrams, tracing faces
[
html notes,
pdf notes,
html notes 2,
pdf notes 2,
scribbles,
video,
Carter 1991
]
[
2020 scribbles,
2020 video,
2020 scribbles 2,
2020 video 2
]
 Feb 8

Winding numbers again, Alexander numbering again, smoothing, unsigned Gauss code planarity, parity (Gauss, Nagy), treeonion figures (Dehn), bipartite interlacement (Rosensteihl)
[
html notes,
pdf notes,
scribbles,
video
]
[
2020 scribbles,
2020 video
]
Planar maps
 Feb 10

Abstract graphs (darts), topological graphs, data structures, embeddings, maps, rotation systems, duality, derived maps
[
html notes,
pdf notes,
scribbles,
video
]
[
2020 scribbles,
2020 video
]
 Feb 15

Deletion and contraction, treecotree decomposition, Euler's formula, discrete GaussBonnet formula
[
html notes,
pdf notes,
scribbles,
sorry no video
]
[
2020 scribbles,
2020 video
]
 Feb 17

Straightline embedding, starshapedhole filling, canonical ordering, Schnyder woods, grid embedding
[
html notes,
pdf notes,
scribbles,
video,
De Fraysseix Pach Pollack 1990,
Schnyder 1990
]
[
2020 scribbles,
2020 video
]
 Feb 22

Equilibrium stresses, Tutte's spring embedding, polyhedral embeddings
[
html notes,
pdf notes,
scribbles,
video
Tutte 1963,
Floater 1997,
Spielman 2018
]
[
2020 scribbles,
2020 video
]
 Feb 24

🆕 The Maxwell–Cremona correspondence: planar frameworks, reciprocal frameworks, polyhedral lifts
[
scribbles,
video,
html notes,
pdf notes
]
 Feb 28
 Paper chase assignment due
Planar paths, cuts, and flows
 Mar 1

Parametric multiplesource shortest paths: shortest paths, slacks, active darts, pivots, disktree lemma, dynamic forest data structures
[
html notes,
pdf notes,
scribbles,
video,
Klein 2005,
Cabello Chambers Erickson 2013
]
[
2020 scribbles,
2020 video
]
 Mar 3
 Class cancelled; Jeff was sick
 Mar 8

🆕 Recursive multiplesource shortest paths: properly shared edges, contraction, distance queries, $O(n)$ vertices at every level of recursion
[
html notes,
pdf notes,
scribbles,
video,
Das, Kipouridis, ProbstGutenberg, WulffNilsen 2022
]
 Mar 10

Separators and $r$divisions: tree separators, fundamental cycles, level separators, cycle separators, good $r$divisions
[
html notes,
pdf notes,
scribbles,
video,
Klein Mozes Sommer 2012,
HarPeled Nayyeri 2018
]
[
2020 scribbles,
2020 video
]
 Mar 18

Undergraduate drop deadline
 Mar 1317
 Spring break — No lectures
 Mar 22

Faster shortest paths: dense distance graphs, generalized nested dissection, sketch of FRBellmanFord
[
html notes,
pdf notes,
scribbles,
video,
Lipton Rose Tarjan 1979,
Fakcharoenphol Rao 2006,
Klein Mozes Weimann 2009
]
[
2020 scribbles,
2020 video
]
 Mar 24
 Faster shortest paths: Monge arrays, SMAWK, FRBellmanFord
Minimum cuts: shortest cycle in dual annulus, MSSP, Reif's divideandconquer algorithm
[
html notes,
pdf notes,
scribbles,
video,
Reif 1983
]
[
2020 scribbles,
2020 video
]
 Skipped

FRDijkstra and faster minimum cuts
[
html notes,
pdf notes,
2020 scribbles,
2020 video,
Fakcharoenphol Rao 2006,
Italiano Nussbaum Sankowski WulffNilsen 2011
]
 Mar 29

Maximum flows: definitions, boundary circulations, Alexander numbering, feasible circulations dual to shortest paths, maxflow by binary search, maxflow via parametric shortest paths
[
incomplete html notes,
incomplete pdf notes,
scribbles,
updated SODA 2011 slides,
video,
Borradaile Klein 2009,
Erickson 2010
]
[
2020 video
]
Surface maps
 Mar 31

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,
]
[
2020 scribbles,
2020 video
]
 Apr 3

Project proposals due
 Apr 5

Overview of submitted project proposals
[
🔒 all proposals,
🔒 video
]
 Apr 7

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,
Conway (via Francis Weeks) 1999
]
[
2020 scribbles,
2020 video
]
 Apr 12

🆕 Treecotree infrastructure 1: Cut graphs, homotopy, crossing and traversal paths, spike and face (bigon and vertex) moves, systems of loops, cycle spaces
[
html notes,
pdf notes,
scribbles,
video,
Erickson HarPeled 2003,
Eppstein 2003
]
 Apr 14

Homotopy testing (Dehn's algorithm):
reduction to system of loops, universal cover, discrete GaussBonnet, Dehn's lemma, radial map, system of quads, (spurs and brackets, runlength encoding)
[
html notes,
pdf notes,
scribbles,
video 1,
video 2,
Lazarus Rivaud 2012,
Erickson Whittlesey 2013
]
[
2020 scribbles,
2020 video
]
 Apr 14

Graduate drop deadline
 Apr 19

🆕 Planarizing and separating surface maps: Menger's theorem, systolic bounds, multicycle separators, depth contours, planarizing subgraphs of size $O(\sqrt{ng})$, (nice $O(n/g)$divisions, fast shortest paths)
[
html notes,
pdf notes,
scribbles,
video (soon),
Eppstein 2003
]
 Apr 21

🆕 Shortest interesting cycles: Contractible vs separating, simplicity, 3path condition, shortestpath crossing, $O(n^3)$ time, dual cutgraph classification, $O(n^2 \log n)$ time
🆕 Homology: Even subgraphs, boundary subgraphs, homology classes, system of cycles, vector spaces, dimension counting
[
html cycles notes,
pdf cycles notes,
html homology notes,
pdf homology notes,
scribbles,
video,
Erickson HarPeled 2004
]
[
2020 scribbles,
2020 video
]
 Apr 21

ICES evaluation forms released
 Apr 26

🆕 Homology, continued: crossing numbers, cohomology, cosnargles, systems of cocycles, homology annotations
🆕 Shortest interesting cycles, continued: Sketch of parametric MSSP, sketch of recursive contraction MSSP, crossing bounds, shortest nonseparating cycle in $O(g^2 n \log n)$ time, (shortest noncontractible cycle)
[
html cycles notes,
pdf cycles notes,
html homology notes,
pdf homology notes,
scribbles,
video,
Cabello Chambers Erickson 2013
]
[
2020 scribbles,
2020 video
]
 Apr 28

Minimum cuts:
duality with minimumweight homologous even subgraph,
homology in surfaces with boundary (forestcotree and treecofrest decompositions),
$\mathbb{Z}_2$homology cover,
minimumweight homologous cycles (MSSP again),
dynamic programming
[
sorry no notes,
scribbles,
video,
Chambers Erickson Fox Nayyeri 2023
]
[
2020 scribbles,
2020 video,
]
 May 3

Maximum flows:
pseudoflows, circulations, boundary circulations, $\mathbb{R}$homology, flow homology basis, feasible boundary circulation $\leftrightharpoons$ shortest paths with negative edges, flow homology polytope, implicit linear progamming, ellipsoid method
[
sorry no notes,
scribbles,
video,
Chambers Erickson Nayyeri 2012
]
[
2020 scribbles,
2020 video,
]
 May 3

Project reports due
 May 4

Last day to submit ICES evaluation forms
 May 5–11
 🔒 Final project presentations
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], 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, Cairnsl, FloaterGostman], 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 by lowdiameter decomposition [Baker, Eppstein], 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 straightline embeddings, geodesic spring embedding [Colin de Verdière oncle, Hass], circle packing [Thurston, Colin de Verdière oncle, Mohar], systolic inequalities, holiest paths and flows, toroidal MaxwellCremona [Erickson Lin], piecewiselinear surfaces, flat surfaces, intrinsic Delaunay triangulations

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, normalcurve tracing [Erickson Nayyeri, Bell], homotopy area [Chambers Wang], more approximation algorithms (an entire course), persistent homology (an entire course)