One-Dimensional Computational Topology

CS 598 JGE, Fall 2020

Main    Schedule    Exercises (pdf)    Projects


For each lecture, I provide links to typeset notes (until I ran out of steam), scribbles ("boardwork"), videos, and other reading/viewing material. (Warning: External links to papers may rot over time.) 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.


Polygons in the plane

Tue Aug 25
Simple polygons: Jordan polygon theorem, point-in-polygon algorithm, trapezoidal decompositions, polygon triangulations
[ html notes, pdf notes, scribbles, video, Eames 1961 ]
Thu Aug 27
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 ]
Tue Sep 1
Homotopy testing: crossing sequences, reduction, uniqueness, homotopy invariance again
[ html notes, pdf notes, scribbles, video ]
Thu Sep 3
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 ]
Tue Sep 8
Shortest homotopic paths
[ html notes, pdf notes, scribbles, video, Leiserson Maley 1985, Hershberger Snoeyink 1994 ]

Planar curves

Thu Sep 10
Immersions, image graphs, homotopy moves, $n$ vertices implies $n+2$ faces, signed Gauss codes, Gauss diagrams, tracing faces
[ html notes, pdf notes, scribbles, video, Carter 1991 ]
Tue Sep 15
Winding numbers, Alexander numbering, smoothing, unsigned Gauss code planarity, parity (Gauss, Nagy), tree-onion figures, bipartite interlacement (Dehn)
[ html notes, pdf notes, scribbles, video ]
Wed Sep 16
Jeff's Graph Drawing talk
Thu Sep 17
Curve contraction: Steinitz's algorithm, rotation number, writhe, defect, (regular homotopy, Whitney–Graustein theorem, strangeness)
[ html notes, pdf notes, scribbles, video, Nowik 2009, Chang Erickson 2017 ]
Mon Sep 21
Paper chase assignment due

Planar maps

Tue Sep 22
Abstract graphs (darts), topological graphs, data structures, embaddings, maps, rotation systems, duality, derived maps
[ html notes, pdf notes, scribbles, video ]
Thu Sep 24
Deletion and contraction, tree-cotree decomposition, Euler's formula, discrete Gauss-Bonnet formula
[ html notes, pdf notes, scribbles, video ]
Tue Sep 29
Straight-line embedding, canonical ordering, Schnyder woods, grid embedding
[ html notes, pdf notes, scribbles, video, De Fraysseix Pach Pollack 1990, Schnyder 1990 ]
Thu Oct 1
Equilibrium stresses, Tutte's spring embedding
[ html notes, pdf notes, scribbles, video, Tutte 1963, Floater 1997, Spielman 2018 ]

Planar paths, cuts, and flows

Tue Oct 6
Multiple-source shortest paths
[ html notes, pdf notes, scribbles, video, Klein 2005, Chambers Cabello Erickson 2013 ]
Thu Oct 8
Separators and $r$-divisions
[ html notes, pdf notes, scribbles, video, Klein Mozes Sommer 2012, Har-Peled Nayyeri 2018 ]
Tue Oct 13
Faster shortest paths, with and without negative edges
[ html notes, pdf notes, scribbles, video, Lipton Rose Tarjan 1979, Fakcharoenphol Rao 2006, Klein Mozes Weimann 2009 ]
Thu Oct 15
Minimum cuts
[ html notes, pdf notes, scribbles, video, Reif 1983 ]
Tue Oct 20
FR-Dijkstra and faster minimum cuts (finished on Thursday)
[ html notes, pdf notes, scribbles, video, Fakcharoenphol Rao 2006, Italiano Nussbaum Sankowski Wulff-Nilsen 2011 ]
Thu Oct 22
Maximum flows
[ updated SODA 2011 slides, video, Borradaile Klein 2009, Erickson 2010 ]

Surface maps

Tue Oct 27
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, scribbles, video ]
Thu Oct 29
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, scribbles, video, Gilbert Hutchinson Tarjan 1984, Sppstein 2003 ]
Fri Oct 30
Project proposals due
Tue Nov 3
Election day — No lecture
Thu Nov 5
Overview of submitted project proposals
[ 🔒 all proposals, 🔒 video ]
Tue Nov 10
Homotopy testing (Dehn's algorithm)
[ html notes, pdf notes, scribbles, video, Lazarus Rivaud 2012, Erickson Whittlesey 2013 ]
Thu Nov 12
Shortest nontrivial cycles
[ sorry no notes, scribbles, video, Erickson Har-Peled 2003, Cabello Chambers Erickson 2013 ]
Tue Nov 17
Minimum cuts and $\mathbb{Z}_2$-homology
[ sorry no notes, scribbles, video, Chambers Erickson Nayyeri 2009, Erickson Nayyeri 2011 ]
Thu Nov 19
Maximum flows and $\mathbb{R}$-homology
[ sorry no notes, scribbles, video, Chambers Erickson Nayyeri 2012 ]
Nov 23–27
Thanksgiving break — No lectures

Stuff and oddments

Tue Dec 1
Approximation schemes via low-diameter slicing: carvings, branchwidth, dynamic programming, radial greedy tree-cotree decomposition, branchwidth ≤ diameter + 1, slicing
[ sorry no notes, scribbles, video, Baker 1994, Eppstein 1999, Demaine Hajiaghayi Mohar 2011 ]
Thu Dec 3
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, scribbles, video; Colin de Verdière, Hubard, de Mesmay 2014; Gilbert Hutchinson Tarjan 1984 ]
Tue Dec 8
Chasing puppies: configuration torus, puppy diagram, essential and contractible critical cycles, human diagram, two essential critical cycles, dexter and sinister strategies, chamfering
[ sorry no notes, scribbles, video; Abrahamsen Erickson Kostitsyna Löffler Miltzow Urhausen Vermeulen Viglietta 2020, Abel Akitaya Demaine Demaine Hesterberg Korman Ku Lynch 2020 ]
Wed Dec 9
Project reports due
Thu Dec 10
Last day to submit ICES evaluation forms
Dec 11–18
🔒 Final project presentations
Fri Dec 18
Extended drop deadline (11:59pm) [info]

Related topics I didn't have time for

This list is far from exhaustive! Topics in bold are the omissions I regret most.

 

Creative Commons License   Powered by MathJax