OneDimensional Computational Topology
All future lecture topics and dates are tentative. In particular, some topics currently slated for a single lecture may take more than one, and others may be dropped entirely due to lack of time or interest.
Links to reading material are in the left margin. Some links lead to preliminary drafts for an evolving textbook, in wildly varying stages of revision, from handwritten notes to rough outlines to shitty first drafts to relatively polished chapters. Other links point to chapters of Philip Klein and Shay Mozes's textbook, and/or relevant research papers. Feedback is welcome, especially if you find mitsakes!
I am recording most of my lectures by using my iPad as a whiteboard; video links are also available in the left margin.
Preliminaries
 Tue Aug 29
[notes, scribbles, video]

Simple polygons: Pricking the garter, Jordan curve theorem [Bolzano], Jordan polygon theorem [Dehn], trapezoidal decompositions, testing whether a point lies in a polygon, polygons have triangulations [almost Gauss, Dehn, Lennes], polygons have ears [Dehn, Meisters], the DehnSchönflies theorem (polygons are disks)
Didn't have time for: polygons with holes, planar straightline graphs, proof of full Jordan curve theorem from Hex [Hein, Nash, Gale, Huneke, Maehara]
 Thu Aug 31
[notes, scribbles, video]

Planar graphs: Definitions, vocabulary, abstract versus topological graphs, data structures, deletion and contraction, spanning trees, planar embeddings, straightline embeddings [Wagner, Fáry, Stein, de Fraysseix et al.], rotation systems [Cayley], polygonal schemata [Cayley/Möbius], duality, treecotree decompositions
 Tue Sep 5
[notes, scribbles, video]

More planar graphs: Schnyder woods, small grid embedding, other straightline embedding theorems (in passing) [Steinitz Tutte Koebe], selfdual data structures, Euler's formula [Descartes], shipwrecks and plagiarism, inductive contractiondeletion proof, von Staudt's treecotree proof, Schnyder woods proof, Cauchy's inductive proof is neither Cauchy's nor a proof
Didn't have time for: Discrete GaussBonnet theorem [Descartes Polya Lyndon Banchoff], but we'll see it later.
Homework 1 released
 Thu Sep 7
[notes, scribbles, video]

Planar curves: Definitions, (at least) three representations, general position, signed crossings, (signed) Gauss codes, planarity of signed Gauss codes [Francis Carter], planarity of unsigned Guass codes, parity [Gauss Nagy], bipartite interleaving [Dehn]
Planar Curves
 Tue Sep 12
[notes, scribbles, video]

Planar curves: Gauss codes redux [Nagy Rosensteihl Tarjan], $O(n)$time algorithm for Dehn's condition [Rosensteihl Tarjan], leftright planarity test [de Fraysseix, Rosensteihl, Ossona de Mendez]
Curve invariants: Fast and Loose, winding number, cycle decompositions, signed vertices, exterior angles [Bradwardine Meister], rotation number, writhe, rot(γ) = 2 wind(γ, γ(0)) + writhe(γ) [Gauss Whitney Titus]
 Thu Sep 14
[old notes, new notes, scribbles, video]
 Curve homotopy: Homotopy definition, triangle moves, face and edeg moves, homotopy moves [Steinitz Alexander Briggs Reidemeister Titus], contracting in $O(n^2)$ moves [Steinitz], regular homotopy, WhitneyGraustein theorem [Boy], regular homotopy in $O(n^2)$ moves, strangeness and defect [Chang Erickson]
Didn't have time for: selfoverlapping curves [Blank Poénaru Shor van Wyk Eppstein Mumford]
 Tue Sep 19
 No class; Jeff is traveling.
Homework 2 released
 Thu Sep 21
 No class; Jeff is traveling.
 Tue Sep 26
[notes]
 Homotopy via crossing sequences: $\alpha \sim \beta$ if and only if $\alpha\cdot\overline\beta$ is contractbile, sentinel points, fences, crossing sequences, elementary reduction, uniqueness, contractible if and only if reduced crossing sequence is empty, $O(nk)$ time for a polygon with $k$ vertices among $n$ obstacle points
I used the blackboard today, so no scribbles or video. Blackboard photos coming soon.
 Thu Sep 28
[notes,
scribbles,
video]
 Testing homotopy: Trapezoidal decomposition, sweepline algorithm, vertical shelling order, replacing coordinates with ranks, rectification preseres crossing sequence, sliding brackets, layered range tree, $O((n+k+s)\log (n+k+s)$ time for $k$gone with $s$ selfintersections among $n$ obstacle points.
 Tue Oct 3
[rough notes,
scribbles,
video]
 Shortest homotopic paths: Problem statement, polygons with holes, geometry matters, triangulation supprts same reduction algorithm, shortest paths in polygons: crossing sequence $\to$ reduction $\to$ sleeve $\to$ funnel = $O(nk)$ time, same algorithm finds homotopic shortest paths by not being clever, covering spaces and covering maps, universal cover, lifting paths and homotopies, loops is contractible iff its universal lifts are loops, "building" the universal cover
Planar Graphs
 Thu Oct 5
[paper,
KM 7,
scribbles,
video]

Multiplesource shortest paths: Problem statement, representing $O(n^2)$ shortest paths using only $O(n)$ space, Treedisk lemma, source interval for each dart, uniqueness, Isolation Lemma, cotree perturbation, leftmost shortest paths, moving source vertex, slack, pivoting in the tensest edge, $O(n)$ pivots, $O(\log n)$ time per pivot via dynamic forest data structures [black box], persistent data structures [black box]
 Tue Oct 10
[notes,
KM 7,
scribbles,
video]
 Planar separators: Grid separators, tree separators, fundamental cycles, BFS levels, $O(\sqrt{n})$ vertices, circle packing [Koebe Andreev Thurston], existential cycle separators [Miller Teng Thuston Vavasis], algorithmic cycle separators [Miller, Klein, Nayyeri HarPeled], $r$divisions, weights and holes, dense distance graphs, singlesource shortest paths in $O(n\log\log n)$ time
Homework 3 released
 Thu Oct 12
["notes",
KM 8,
SMAWK notes,
scribbles,
video]
 Shortest paths with negative edge lengths: Separator, repricing, BellmanFord on separator, repricing again, MSSP removes one $O(n^{3/2})$ term, Monge arrays, monotonicity of row minima, SMAWK, KlaweKleitman, decomposing into Monge arrays, FRBellmanFord in $O(n\alpha(n))$ time, $O(n\log^2 n)$ time dominated by MMPP+recursion
 Tue Oct 17
["notes",
scribbles,
video]
 Minimum cuts: cut/cycle duality, winding numbers and homotopy revisited, crossing bound, nonsimple crossings, call Dijkstra k times in $O(kn\log n)$ time, divideandconquer with Dijkstra in $O(n\log n\log k)$ time [Reif], MSSP in $O(n\log n)$ time [Klein], with lineartime shortest paths in $O(n\log k)$ time
 Thu Oct 19
[paper,
"notes",
scribbles,
video]
 Faster minimum cuts: Monge heaps [Fakcharoenphol Rao]: reveal column, minimum visible element, hide row; nice $r$divisions; building a dense distance graph in $O(n\log r)$ time; FRDijkstra: $O((n/\sqrt{r})(\log^2 r + \log n))$ time; minimum cut in $O(n\log\log n)$ time [Italiano Nussbaum Sankowski WulffNilsen]
 Tue Oct 24
["notes",
paper,
KM 10,
scribbles,
video]
 Maximum flows: Antisymmetric flow formulation; Flow/shortest path duality, FordFulkerson uppermost path, Hassin's reduction from $st$planar maxflow to shortest paths, uppermost path is dual to Dijkstra, Venkatesan's reduction from feasible flow to shortest paths with negative lengths, slack = residual capacity, parametric shortest paths, winding numbers
 Thu Oct 26
["notes",
paper,
KM 10,
scribbles,
video]
 Maximum flows, continued: Treecotree decomposition again, active edges lie on a dual path, decreasing slack = pushing flow, leftmost augmenting path [Borradaile Klein], a bit of network simplex, $O(n\log n + N\log n)$ time for $N$ pivots, universal cover $\tilde{G}$, any path $p$ from $o$ to $v$ in $G$ lifts to a path from $o_i$ to $v_{i+\pi(p)}$ in $\tilde{G}$, universal shortest path tree, disktree lemma again, each dart pivots into $T_\lambda$ at most once
 Tue Oct 31
["notes",
KM 14,
scribbles,
video]
 Local approximation schemes: carving, branch decomposition, branchwidth, maximum independent set in $O(4^{bw} n)$ time via dynamic programming [Boedlander], worstcase planar branchwidth $\Theta(\sqrt{n})$, planar max independent set in $2^{O(\sqrt{n})}$ time, radial graph $G^\times$ and medial graph $G^\diamond$ [Tait, Steinitz], $diam(G^\diamond) \le 2\min\{diam(G), diam(G^*)\}$, branch decomposition from greedy medial treecotree decomposition, $bw(G) \le diam(G^\diamond)/2 + 1$ [Tamaki], slicing into disjoint lowdiameter subgraphs [Baker], $(1\varepsilon)$max independent set in $O(n\cdot 4^{1/\varepsilon})$ time, cover with overlapping lowdiameter subgraphs; $(1+\varepsilon)$min vertex cover in $O(n\cdot 4^{1/\varepsilon})$ time
 Thu Nov 2
 No class today; work on your project proposals.
Stuff on Surfaces
 Tue Nov 7
["notes",
old notes,
old notes,
scribbles,
video]

Surface maps: 2manifolds, surface maps, Möbius no Listing no really Möbius okay maybe Gauss bands [alJazari], orientability, Fortunatus' Purse, signed polygonal schemata, cellular graph embeddings, signed rotation systems, flags/blades/vanes, reflection systems [Tutte, Coxeter], more data structures
The old notes describe signed rotation systems, which are another standard representation of nonorientable surface maps. But I think reflection maps are more natural, despite being slightly more verbose.
 Thu Nov 9
["notes",
old notes,
old notes,
scribbles,
video]

More surface maps: duality, deletion and contraction, treecotree decomposition, contracting loops, deleting isthmuses, handles and twists, Dyck's surface, systems of loops, surface classification, "Oiler's formula", maps with boundary, punctured maps, treecoforest and forestcotree decompositions, systems of arcs, homotopy testing in surfaces with boudnary
 Tue Nov 14
 Overview of submitted project proposals
 Thu Nov 16
["notes",
paper
scribbles,
video]

Homotopy testing: surfaces with boundary (system of arcs + crossing sequence reduction), reduce to system of loops in $O(n + g\ell)$ time, sequence reduction is more complex, spur moves and face moves, universal cover, regular hyperbolic tiling, hyperbolic isometry, combinatorial GaussBonnet, Dehn's lemma: Any nonsimple contractible cycle can be locally shortened [Dehn 1912], Dehn's algorithm, naive $O(g^3 \ell)$ time, $O(g\ell)$ time using a DFA, reduce to system of quads in $O(n + \ell)$ time, turn sequences, spurs ($0$) and brackets ($1\, 2^*\, 1$ or $1\, {2}^*\, {1}$), run length encoding, reduction in $O(\ell)$ time [LazarusRivaud, EWhittlesey]
 Tue Nov 21
 Thanksgiving break
 Thu Nov 23
 Thanksgiving break
 Tue Nov 28
["notes",
paper
scribbles,
video]
 Shortest nontrivial cycles: noncontractible vs nonseparating, edgewidth/facewidth/systole, Thomassen's threepath condition, shortestpath crossing, greedy treecotree decomposition, $O(n^2 \log n)$ time, cut graphs, crossing sequences [Kutz], multiplesource shortest paths [Cabello Chambers Erickson]
Didn’t have time for details of MSSP: grove decompositions, treeboundary lemma again, $O(g^2 n\log n)$ time with high probability, $O(g^3 n\log n)$ or $O(g^2 n\log^2 n)$ time worstcase, uniqueness
 Thu Nov 30
["notes",
paper
scribbles,
video]
 Minimum cuts: cutboundary duality, even subgraphs, $\mathbb{Z}_2$homology, $\mathbb{Z}_2$homology cover, minimum cuts in $2^{O(g)}n\log n$ time, NPhardness
Didn’t have time for shortest homotopic paths: Tight octagonal decompositions, hyperbolic isoperimetry again, reduced crossing sequences, relevant chunk of universal cover
 Fri Dec 1
[makeup lecture]
["notes",
paper
scribbles,
video]

Maximum flows: $\mathbb{R}$homology, implicit optimization, ellipsoid method [Katchiyan, GrötschelLovászSchrijver], randomwalk sampling [BerstimasVempala], maximum flows in $O(g^5 n \log^2 n\log C)$ time [sketch]
 Tue Dec 5
[scribbles,
video]

Separators and planarization: optimal cut graphs, approximate cut graphs, cutting cycles, balanced separators, $r$divisions, Monge structures for pieces with holes, fast shortest paths with negative weights
 Thu Dec 7
[notes,
scribbles,
video]
 Graph minors: KuratowskiWagner, Graph Minor theorem [Robertson Seymour], minorclosed families, finite obstruction sets, planar minor xor bounded treewidth
Didn’t have time for: flat grids, genus approximation [Siridopoulos et al], Graph Structure Theorem [Robertson Seymour]
 Fri Nov 8
[makeup lecture]
[paper,
scribbles,
truncated video]

Curve homotopy on surfaces: homotopy moves, loops and bigons again [Hass Scott], $\Theta(n^2)$ moves to remove all crossings, $O(n^4)$ moves to remove as many crossings as possible
[Video only captures last 30 minutes.]
 Tue Dec 12
["notes",
paper (eventually),
scribbles,
video]
 Trivial closed walks in directed surface graphs, or “A paper from the future” or “What I did this semester in my Copious Spare Time™” or “How can you possibly not know if that's decidable?”
 Finals week
 Project presentations
Topics I didn’t have time for
This list is far from exhaustive, as are the references for each topic!
Curves in the plane
 ❌

Other cool stuff: Curve simplification, curveshortening flow, weakly simple polygons [Minc, Skopenkov], Fréchet distance [Alt Godau], mountain climbing [Homma, Huneke], linkages, Carpenter's rule theorem [Connelly Demaine Rote, Streinu], shortest noncrossing walks, minimum area homotopy [Chanbers Wang, Fasy Karakoc Wenk, Nie]
 ❌

Open problems: Monotone homotopy in $o(n^2)$ moves, inscribed squares
Planar graphs
 ❌

PTAS by decomposition: TSP, Steiner tree, and the like
 ❌

PTAS by local search: bisection, $k$center, and the like [CohenAddad Klein Mathieu]
 ❌

Other cool stuff: enumeration/sampling [Tutte]; squared rectangles [Dudeney Dehn Brooks Tutte...]; circle packing [Koebe Andreev Thurston]; MaxwellCremona equilibrium/stress duality; maximum cut via matchings [Hadlock]; planar graph isomorphism [Weinberg Hopcroft Tarjan Wong]; OkamuraSeymour theorem; crossing lemmas [Ajtai Chvátal Newborn Szemerédi Leighton]; spanners; approximate distance oracles; multiterminal maximum flow; electrical reduction; string graphs
 ❌

Open problems: Squidsort, vertexdisjoint paths, fast minimumcost flow, fast electrical reduction, polyhedral unfolding
Surface curves/graphs
 ❌

PTASs for NPhard problems: deletion decomposition [Djidjev Gilbert Hutchinson Tarjan], contraction decomposition [Klein Demaine Hajiaghayi Mohar], BakerEppstein, brick decomposition, bidimensionality
 ❌

Other cool stuff: Map isomorphism, graph isotopy testing [Ladegaillerie, Colin de Vèrdiere, de Mesmay], normalcurve tracing/flipping [ShaeferSedgwickŠtefankovič, ENayyeri, BellSchleimer], geometric intersection numbers [Despré Lazarus], weak HananiTutte theorem [Pelsmajer Schaefer Štefankovič]
 ❌

Open problems: correct and implementable $O(n)$time toroidal embedding; genus of unsigned Gauss codes; faster disjoint paths/flows; detecting negative contractible closed walks in directed surface graphs