CS 598: Computational Topology (Spring 2013)
Schedule
All future lecture topics and dates are tentative. In particular, some topics 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. Most 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. Feedback is welcome, especially if you find mitsakes!
- Tue Jan 15
[notes]
-
Simple polygons: The Jordan curve theorem [Bolzano], trapezoidal decompositions, testing whether a point lies in a polygon, polygons have triangulations [Dehn, Lennes], polygons have ears [Dehn, Meisters], the Dehn-Schönflies theorem (polygons are disks), polygons with holes, planar straight-line graphs
- Thu Jan 17
[notes]
-
Planar graphs: Definitions, vocabulary (vertex, dart, head/tail, reversal, edge, simple, loop, bridge,...), topological graphs, data structures, deletion and contraction, spanning trees, planar embeddings, rotation systems, straight-line embeddings [Steinitz, Wagner, Fáry, de Fraysseix et al.], Schnyder woods, grid embedding
- Tue Jan 22
[notes]
-
Planar maps: faces, next = rev $\circ$ succ, combinatorial maps, dual maps, not "dual graphs", self-dual data structures, duality dictionary (vertex $\rightleftharpoons$ face, succ $\rightleftharpoons$ next, head $\rightleftharpoons$ left, counterclockwise $\rightleftharpoons$ clockwise, delete $\rightleftharpoons$ contract, loop $\rightleftharpoons$ bridge, cycle $\rightleftharpoons$ bond, spanning tree $\rightleftharpoons$ spanning cotree, ...), tree-cotree decomposition, Euler's formula [Descartes], shipwrecks and plagiarism, von Staudt's tree-cotree proof,
Cauchy's Meister's Karsten's incomplete inductive proof, shelling orders exist, minimum/maximum spanning trees in O(m) time [Broůvka, Cheriton-Tarjan, Matsui, Mareš].
- Thu Jan 24
[notes]
-
Homotopy: Coffee cups are donuts, VLSI river routing, map simplification, definitions, reparametrization, invariance, 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
- Tue Jan 29
[notes]
-
Homotopy: Homotopy of cycles and arcs, sentinel points, testing contractibility in $O(n + h\log h + hk)$ time, trapezoidal decompositions again, rectification, sliding brackets, Chazelle's segment-dragging 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
- Thu Jan 31
[notes soon]
-
Shortest homotopic paths: Shortest paths in polygons, reduced crossing sequences, parity, sleeves, the funnel algorithm [Tompa, Chazelle, Lee-Preparata, Leierson-Maley], polygons with holes, covering spaces, universal cover, induced triangulations, boundary-triangulated 2-manifolds, funnels still work, subtleties with sentinel points
- skipped
[notes]
-
Regular homotopy: regular closed curves, winding and rotation numbers, signed crossings, cycle decompositions, happy points and sad points, regular homotopy, The Whitney-Graustein theorem, elementary moves, canonical regular curves, $O(n^2)$ moves always suffice, strangeness, $\Omega(n^2)$ moves are sometimes necessary
- Tue Feb 5
[notes soon]
-
Surface maps: 2-manifolds, surface maps, Fortunatus' Purse, signed polygonal schemata, cellular graph embeddings, signed rotation systems, band decompositions, blades/flags, reflection systems, duality, data structures, Möbius no Listing no really Möbius or maybe Gauss bands, orientability
- Thu Feb 7
[notes soon]
-
More surface maps: duality dictionary (blade $\rightleftharpoons$ blade, dart $\rightleftharpoons$ side, cycle $\rightleftharpoons$ cocycle, edge cut $\rightleftharpoons$ boundary subgraph, ...), deletion and contraction, tree-cotree decomposition, contracting loops, deleting isthmuses, handles and twists, Dyck's surface, surface classification, "Oiler's formula", maps with boundary, punctured maps, tree-coforest and forest-cotree decompositions
- Tue Feb 12
[paper]
-
Surface homotopy: recall definitions, edge moves and face moves, disk diagrams, universal cover, system of loops, hyperbolic tiling, combinatorial Gauss-Bonnet theorem, Dehn's lemma (Every nontrivial noncontractible cycle in a system of loops has either a spur or most of a face boundary)
- Thu Feb 14
[paper]
-
Surface homotopy: Dehn's algorithms, contractibility in $O(g n + g^2 \ell)$ time, system of quads, spurs and brackets, run-length-encoded turn sequences, reduced paths and cycles, contractibility in $O(n + \ell)$ time, canonical paths and cycles, free homotopy in $O(n + \ell)$ time
- Tue Feb 17
[paper]
-
Shortest nontrivial cycles: non-contractible vs non-separating, edgewidth/facewidth/systole, Thomassen's three-path condition, modified Dijkstra, $O(n^2 \log n)$ time, crossing shortest paths, cutting into disks, cut graphs, crossing sequences, $2^{O(g)} n\log n$ time [Kutz 2007]
- Thu Feb 19
[paper]
-
Multiple-source shortest paths: problem statement, parametric shortest paths, kinetic data structures, dynamic forests, pivots, $O(n \log n)$ time in planar graphs [Klein 2005], $O(n)$ time in undirected unweighted planar graphs [Eisenstadt and Klein 2013], grove decompositions, $O(g^2 n\log n)$ time in surface graphs
- Tue Feb 24
[paper]
-
Minimum cuts: planar cut-cycle duality, $O(n\log n)$ time in undirected planar graphs [Reif 1985], cut-boundary duality, even subgraphs, $\mathbb{Z}_2$-homology, $\mathbb{Z}_2$-homology cover, $2^{O(g)}n\log n$ time in undirected surface graphs, more recent advances
- Tue Feb 26
[paper 1]
[paper 2]
-
Maximum flows: planar flow-shortest-path duality, parametric shortest paths again, $O(n \log n)$ time in planar graphs [Borradaile Klein 2008], $O(n)$ in unweighted planar graphs [Weihe 1994, Eisenstadt and Klein 2013], $\mathbb{R}$-homology, implicit optimization, ellipsoid method, $O(g^8 n \log^2 n\log^2 C)$ time, ha ha yeah right.
- Tue Mar 5
- Guest lecture — Jeff is out of town
- Tue Mar 7
- Guest lecture — Jeff is out of town
- ??
- Contour trees and Reeb graphs
- ??
- Balanced separators
- ??
- Treewidth decompositions
- ??
- Forbidden minors
- ??
- Discrete Morse theory
- ??
- Discrete differential geometry
- ??
- Simplicial and other complexes
- ??
- Distributed computing
- ??
- Homology
- ??
- Persistent homology
- ??
- Project presentations
