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.
Lecture notes are available for some topics—look for links in the left margin. Many of these notes are preliminary drafts for an evolving textbook, in wildly varying stages of revision, from rough outlines to shitty first drafts to relatively polished chapters; in a few cases, I point directly to published papers instead of notes. Feedback is welcome, especially if you find mitsakes!
>I am recording my lectures by using my iPad as a whiteboard; video links are 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]
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
 Homotopy via crossing sequences: Crossing words, reduction
 Thu Sep 28
 Testing homotopy: Sliding brackets
 Tue Oct 3
 Shortest homotopic paths: Funnels, universal cover
 Thu Oct 5

Planar Graphs
 Tue Oct 10

 Thu Oct 12

 Tue Oct 17

 Thu Oct 19

 Tue Oct 24

 Thu Oct 26

 Tue Oct 31

 Thu Nov 2

 Tue Nov 7

 Thu Nov 9

Curves and Graphs on Surfaces
 Tue Nov 14

 Thu Nov 16

 Tue Nov 21
 Thanksgiving break
 Thu Nov 23
 Thanksgiving break
 Tue Nov 28

 Thu Nov 30

 Tue Dec 5

 Thu Dec 7

 Tue Dec 12

 Makeup (TBA)

 Makeup (TBA)

 Finals week
 Project presentations
Future topics in no particular order
I definitely won't cover everything in this list, and I expect to cover topics that aren't on this list. Some of these topics would require multiple lectures to cover in useful detail. References in this list are not meant to be exhaustive.
Curves in the plane
 🔜

Homotopy via crossing sequences: Equivalence classes, fundamental group $\pi_1(X,x)$, simple polygons are boring, polygons with holes, crossing sequences, elementary reductions, every string has a unique reduction, testing contractibility in $O(n\log n + nk)$ time, loops with empty reduced crossing sequences are contractible (easy), canonical paths, skeleton, deformation retraction, contractible loops have empty reduced crossing sequences (hard), hey look some actual topology, homotopies can be ugly but wlog they're nice, sentinel points,
 🔜

Efficient homotopy: Homotopy of cycles and arcs, testing contractibility in $O(n + h\log h + hk)$ time, trapezoidal decompositions again, rectification, sliding brackets, Chazelle's segmentdragging data structure, testing contractibility of simple loops in $O(n + (h+k)\log h)$ time, comparing intersecting simple paths, pins vs pushpins vs tacks, bundling
 🔜

Shortest homotopic paths: Shortest paths in polygons, reduced crossing sequences, parity, sleeves, the funnel algorithm [Tompa, Chazelle, LeePreparata, LeiersonMaley], polygons with holes, covering spaces, universal cover, induced triangulations, boundarytriangulated 2manifolds, funnels still work, subtleties with sentinel points
 🔜

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
 🔜

Structure: Whitney's duality theorem, Steinitz's theorem, Tutte's theorem, circlepacking [Koebe Andreev Thurston], HananiTutte theorem [Hanani, van Kampen, Tutte, Shapiro, Wu], leftright planarity testing [de Fraysseix, Rosenstiehl, Ossona de Mendez], Schnyder woods, forbidden minors [Kuratowski Wagner]
 🔜

Planar separators: Menger's theorem, LiptonTarjan, via circle packing, cycle separators [Miller], $r$divisions, hierarchical separators, $O(n)$time hierarchy construction [Klein Mozes Sommer]
 🔜

Multiplesource shortest paths: problem statement, parametric shortest paths, kinetic data structures, dynamic forests, pivots, disksubtree lemma, $O(n \log n)$ time in planar graphs [Klein Cabello Chambers], $O(n)$ time in undirected unweighted planar graphs [Eisenstadt Klein]
 🔜

Fast shortest paths: nonnegative edge lengths [sketch], Monge condition [Fakcharoenphol Rao], SMAWK, Monge heaps, densedistance graphs, FRDijkstra, negative edge lengths [Klein Mozes Weimann WulffNilsen]
 🔜

Minimum cuts: cutcycle duality [Whitney], $O(n\log n)$ time [Reif 1985], $O(n\log \log n)$ time [Italiano et al.]
 🔜

Maximum flows: planar flowshortestpath duality, parametric shortest paths again, $O(n \log n)$ time in planar graphs [Borradaile Klein], $O(n)$ in unweighted planar graphs [Weihe Eisenstadt Klein]
 🔜

Treewidth and branchwidth: tree decompositions, dynamic programming [Boedlander], carving decompostions; slicing [Baker]; treewidth vs. diamater [Eppstein]; contraction [Klein]; medial and radial graphs [Tait, Steinitz]; branchwidth vs. radius [Tamaki]; PTASes for vertex cover, independent set, and TSP
 🔜

PTAS by local search [CohenAddad Klein Matieu]
 🔜

Other cool stuff: enumeration/sampling [Tutte]; squared rectangles [Dudeney Dehn Brooks Tutte...]; maximum cut via matchings [Hadlock]; planar graph isomorphism [Weinberg Hopcroft Tarjan Wong]; OkamuraSeymour theorem; crossing lemma [Ajtai Chvátal Newborn Szemerédi Leighton]; spanners; approximate distance oracles; approximating subset TSP and Steiner tree; approximating ATSP; multiterminal maximum flow; electrical reduction; string graphs
 🔜

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

Surface maps: 2manifolds, surface maps, Möbius no Listing no really Möbius or maybe Gauss bands, orientability, Fortunatus' Purse, signed polygonal schemata, cellular graph embeddings, signed rotation systems, flags/blades/vanes, reflection systems [Tutte], more data structures
 🔜

More surface maps: duality, deletion and contraction, treecotree decomposition, contracting loops, deleting isthmuses, handles and twists, Dyck's surface, surface classification, "Oiler's formula", maps with boundary, punctured maps, treecoforest and forestcotree decompositions
 🔜

Surface homotopy: recall definitions, edge moves and face moves, universal cover, system of loops, hyperbolic tiling, disk diagrams, combinatorial GaussBonnet theorem, Dehn's algorithms, contractibility in $O(g n + g^2 \ell)$ time, system of quads, spurs and brackets, runlengthencoded turn sequences, reduced paths and cycles, contractibility in $O(n + \ell)$ time, canonical paths and cycles, free homotopy in $O(n + \ell)$ time
 🔜

More surface homotopy: 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
 🔜

Shortest nontrivial cycles: noncontractible vs nonseparating, edgewidth/facewidth/systole, Thomassen's threepath condition, modified Dijkstra, $O(n^2 \log n)$ time, crossing shortest paths, cutting into disks, cut graphs, crossing sequences [Kutz], multiplesource shortest paths, grove decompositions, treeboundary lemma, $O(g^2 n\log n)$ time
 🔜

Minimum cuts and maximum flows: cutboundary duality, even subgraphs, $\mathbb{Z}_2$homology, $\mathbb{Z}_2$homology cover, minimum cuts in $2^{O(g)}n\log n$ time, $\mathbb{R}$homology, implicit optimization, ellipsoid method, maximum flows in $O(g^8 n \log^2 n\log^2 C)$ time [sketch].
 🔜

Planarization: Cutting cycles, deletion decomposition [Djidjev Gilbert Hutchinson Tarjan], contraction decomposition [Klein Demaine Hajiaghayi Mohar], balanced separators, BakerEppstein, fast shortest paths with negative weights
 🔜

Graph minors: KuratowskiWagner, Graph Minor theorem [Robertson Seymour], minorclosed families, finite obstruction sets, planar minor xor bounded treewidth, flat grids, genus approximation [Siridopoulos et al], Graph Structure Theorem [Robertson Seymour]
 🔜

Other cool stuff: Map isomorphism, graph isotopy testing [Ladegaillerie, Colin de Vèrdiere, de Mesmay], normalcurve tracing/flipping [Shaefer Sedgwick Štefankovič Nayyeri Bell Schleimer], 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