One-Dimensional Computational Topology

CS 598 JGE, Fall 2017

Main    Schedule    Homework    Projects    References

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 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.


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 Dehn-Schönflies theorem (polygons are disks)

Didn't have time for: polygons with holes, planar straight-line 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, straight-line embeddings [Wagner, Fáry, Stein, de Fraysseix et al.], rotation systems [Cayley], polygonal schemata [Cayley/Möbius], duality, tree-cotree decompositions

Tue Sep 5
[notes, scribbles, video]
More planar graphs: Schnyder woods, small grid embedding, other straight-line embedding theorems (in passing) [Steinitz Tutte Koebe], self-dual data structures, Euler's formula [Descartes], shipwrecks and plagiarism, inductive contraction-deletion proof, von Staudt's tree-cotree proof, Schnyder woods proof, Cauchy's inductive proof is neither Cauchy's nor a proof

Didn't have time for: Discrete Gauss-Bonnet 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], left-right 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, Whitney-Graustein theorem [Boy], regular homotopy in $O(n^2)$ moves, strangeness and defect [Chang Erickson]

Didn't have time for: self-overlapping 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: $\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, sweep-line 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$ self-intersections 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]
Multiple-source shortest paths: Problem statement, representing $O(n^2)$ shortest paths using only $O(n)$ space, Tree-disk 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 Har-Peled], $r$-divisions, weights and holes, dense distance graphs, single-source 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, Bellman-Ford on separator, repricing again, MSSP removes one $O(n^{3/2})$ term, Monge arrays, monotonicity of row minima, SMAWK, Klawe-Kleitman, decomposing into Monge arrays, FR-Bellman-Ford 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, divide-and-conquer with Dijkstra in $O(n\log n\log k)$ time [Reif], MSSP in $O(n\log n)$ time [Klein], with linear-time 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; FR-Dijkstra: $O((n/\sqrt{r})(\log^2 r + \log n))$ time; minimum cut in $O(n\log\log n)$ time [Italiano Nussbaum Sankowski Wulff-Nilsen]
Tue Oct 24
["notes", paper, KM 10, scribbles, video]
Maximum flows: Antisymmetric flow formulation; Flow/shortest path duality, Ford-Fulkerson 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: Tree-cotree 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, disk-tree 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], worst-case 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 tree-cotree decomposition, $bw(G) \le diam(G^\diamond)/2 + 1$ [Tamaki], slicing into disjoint low-diameter subgraphs [Baker], $(1-\varepsilon)$-max independent set in $O(n\cdot 4^{1/\varepsilon})$ time, cover with overlapping low-diameter 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
Surface maps: 2-manifolds, surface maps, Möbius no Listing no really Möbius okay maybe Gauss bands [al-Jazari], orientability, Fortunatus' Purse, signed polygonal schemata, cellular graph embeddings, signed rotation systems, flags/blades/vanes, reflection systems [Tutte], more data structures
Thu Nov 9
More surface maps: duality, deletion and contraction, tree-cotree decomposition, contracting loops, deleting isthmuses, handles and twists, Dyck's surface, systems of loops, surface classification, "Oiler's formula", maps with boundary, punctured maps, tree-coforest and forest-cotree decompositions, systems of arcs
Tue Nov 14
Overview of submitted project proposals
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

Potential future topics and Past skipped topics

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

Other cool stuff: Curve simplification, curve-shortening 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 non-crossing 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 [Cohen-Addad 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]; Okamura-Seymour theorem; crossing lemma [Ajtai Chvátal Newborn Szemerédi Leighton]; spanners; approximate distance oracles; approximating subset TSP and Steiner tree; approximating ATSP; multi-terminal maximum flow; electrical reduction; string graphs
Open problems: Squidsort, vertex-disjoint paths, fast minimum-cost flow, fast electrical reduction, polyhedral unfolding

Surface curves/graphs

Surface maps: 2-manifolds, 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, 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
Surface homotopy: recall definitions, edge moves and face moves, universal cover, system of loops, hyperbolic tiling, disk diagrams, combinatorial Gauss-Bonnet theorem, 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
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: 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 [Kutz], multiple-source shortest paths, grove decompositions, tree-boundary lemma, $O(g^2 n\log n)$ time
Minimum cuts and maximum flows: cut-boundary 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, Baker-Eppstein, fast shortest paths with negative weights
Graph minors: Kuratowski-Wagner, Graph Minor theorem [Robertson Seymour], minor-closed 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], normal-curve tracing/flipping [Shaefer Sedgwick Štefankovič Nayyeri Bell Schleimer], geometric intersection numbers [Despré Lazarus], weak Hanani-Tutte theorem [Pelsmajer Schaefer Štefankovič]
Open problems: correct and implementable $O(n)$-time toroidal embedding; genus of unsigned Gauss codes; faster disjoint paths/flows


Creative Commons License   Powered by MathJax