One-Dimensional 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.) Past 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.)
All future lecture topics are tentative, especially in the last section. The current topic schedule mirrors lectures I gave in Fall 2020.
Polygons in the plane
- Jan 18
-
Simple polygons: Jordan polygon theorem, point-in-polygon algorithm, trapezoidal decompositions, polygon triangulations
[
html notes,
pdf notes,
scribbles,
video,
Eames 1961
]
[
2020 scribbles,
2020 video
]
- Jan 20
-
Winding numbers: Fast and Loose, non-simple 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), tree-onion 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, tree-cotree decomposition, Euler's formula, discrete Gauss-Bonnet formula
[
html notes,
pdf notes,
scribbles,
sorry no video
]
[
2020 scribbles,
2020 video
]
- Feb 17
-
Straight-line embedding, star-shaped-hole 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 multiple-source shortest paths: shortest paths, slacks, active darts, pivots, disk-tree 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 multiple-source shortest paths
[
html notes,
pdf notes,
Das, Kipouridis, Probst-Gutenberg, Wulff-Nilsen 2022
]
- Mar 10
-
Separators and $r$-divisions
[
html notes,
pdf notes,
2020 scribbles,
2020 video,
Klein Mozes Sommer 2012,
Har-Peled Nayyeri 2018
]
- Mar 18
-
Undergraduate drop deadline
- Mar 13-17
- Spring break — No lectures
- Mar 22
-
Faster shortest paths, with and without negative edges
[
html notes,
pdf notes,
2020 scribbles,
2020 video,
Lipton Rose Tarjan 1979,
Fakcharoenphol Rao 2006,
Klein Mozes Weimann 2009
]
- Mar 24
-
Minimum cuts
[
html notes,
pdf notes,
2020 scribbles,
2020 video,
Reif 1983
]
- Skip?
-
FR-Dijkstra and faster minimum cuts
[
html notes,
pdf notes,
2020 scribbles,
2020 video,
Fakcharoenphol Rao 2006,
Italiano Nussbaum Sankowski Wulff-Nilsen 2011
]
- Mar 29
-
Maximum flows
[
updated SODA 2011 slides,
2020 video,
Borradaile Klein 2009,
Erickson 2010
]
Surface maps
- Mar 31
-
Surface maps: 2-manifolds, polygonal schemata, cellular embeddings and rotation systems, orientation and genus, band decompositions, reflection systems, deletion and contraction
[
html notes,
pdf notes,
2020 scribbles,
2020 video
]
- Apr 3
-
Project proposals due
- Apr 5
-
Overview of submitted project proposals
[
🔒 all proposals,
🔒 2020 video
]
- Apr 7
-
Surface classification: Kerékjártó-Rado theorem, tree-cotree decompositions, systems of loops, handles, twists, Dyck's surface, classification, Euler characteristic, discrete Gauss-Bonnet
[
html notes,
pdf notes,
2020 scribbles,
2020 video,
Gilbert Hutchinson Tarjan 1984,
Eppstein 2003
]
- Apr 12
-
Homotopy testing (Dehn's algorithm)
[
html notes,
pdf notes,
2020 scribbles,
2020 video,
Lazarus Rivaud 2012,
Erickson Whittlesey 2013
]
- Apr 14
-
Shortest nontrivial cycles
[
sorry no notes,
2020 scribbles,
2020 video,
Erickson Har-Peled 2003,
Cabello Chambers Erickson 2013
]
- Apr 14
-
Graduate drop deadline
- Apr 19
-
Minimum cuts and $\mathbb{Z}_2$-homology
[
sorry no notes,
2020 scribbles,
2020 video,
Chambers Erickson Nayyeri 2009,
Erickson Nayyeri 2011
]
- Apr 21
-
Maximum flows and $\mathbb{R}$-homology
[
sorry no notes,
2020 scribbles,
2020 video,
Chambers Erickson Nayyeri 2012
]
Miscellanea
- Apr 26
-
Approximation schemes via low-diameter slicing: carvings, branchwidth, dynamic programming, radial greedy tree-cotree decomposition, branchwidth ≤ diameter + 1, slicing
[
sorry no notes,
2020 scribbles,
2020 video,
Baker 1994,
Eppstein 1999,
Demaine Hajiaghayi Mohar 2011
]
- Apr 28
-
Planarizing and separating surface maps: Menger's theorem, systolic bounds, multi-cycle separators $O(\sqrt{ng}\log g)$, unstructored separators $O(\sqrt{ng})$
[
sorry no notes,
2020 scribbles,
2020 video;
Colin de Verdière, Hubard, de Mesmay 2014;
Gilbert Hutchinson Tarjan 1984
]
- May 3
-
TBA
- 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 in 2019
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: self-overlapping curves, homotopy area
-
Planar map structures:
Forbidden minors [Kuratowski, Wagner], Steinitz's theorem (Tutte-Maxwell or via medial curve simplification), Alexandrov's theorem, Koebe-Andreev-Thurston circle-packing, squared rectangles [Dudeney, Dehn, Brooks Tutte, ...], electrical reduction [Kennelly, Steinitz, Feo Provan, Truemper, ...], Hanani-Tutte theorem, Okamura-Seymour theorem, crossing lemmas [Ajtai Chvátal Newborn Szemerédi Leighton], rigidity, pseudo-triangulations, 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, Gomory-Hu trees, multi-terminal 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 [Thurston, Colin de Verdière oncle, Mohar], shortest-path embeddings, systolic inequalities, holiest paths and flows, toroidal Maxwell-Cremona [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, Gomory-Hu trees, homotopy area [Chambers Wang], more approximation algorithms (an entire course), persistent homology (an entire course)
