One-Dimensional Computational Topology

CS 598 JGE, Spring 2023

Main    Schedule    Exercises (pdf)    Projects


For each lecture, I provide links to typeset notes (at least until I run out of steam), scribbles ("boardwork"), videos, and other reading/viewing material. (Warning: External links to papers rot over time.) Past 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. (Lecture videos from 2020 are also available.)

All future lecture topics are tentative. The current topic schedule mirrors lectures I gave in Fall 2020.


Polygons in the plane

Jan 18
Simple polygons: Jordan polygon theorem, point-in-polygon algorithm, trapezoidal decompositions, polygon triangulations
[ html notes, pdf notes, scribbles, video, Eames 1961 ]
[ 2020 scribbles, 2020 video ]
Jan 20
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 ]
[ 2020 scribbles, 2020 video ]
Jan 25
Homotopy testing: crossing sequences, reduction, uniqueness, homotopy invariance again
[ html notes, pdf notes, scribbles, video, ]
[ 2020 scribbles, 2020 video ]
Jan 27
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 ]
[ 2020 scribbles, 2020 video, ]
Feb 1
Shortest homotopic paths: triangulation, crossing sequences, reduction, the funnel algorithm, holes for free!
[ html notes, pdf notes, scribbles, video, Leiserson Maley 1985, Hershberger Snoeyink 1994 ]
[ 2020 scribbles, 2020 video, ]

Planar curves

Feb 3
Immersions, image graphs, homotopy moves, $n$ vertices implies $n+2$ faces, signed Gauss codes, Gauss diagrams, tracing faces
[ html notes, pdf notes, 2020 scribbles, 2020 video, Carter 1991 ]
Feb 8
Winding numbers, Alexander numbering, smoothing, unsigned Gauss code planarity, parity (Gauss, Nagy), tree-onion figures, bipartite interlacement (Dehn)
[ html notes, pdf notes, 2020 scribbles, 2020 video ]
Feb 10
Curve contraction: Steinitz's algorithm, rotation number, writhe, defect, (regular homotopy, Whitney–Graustein theorem, strangeness)
[ html notes, pdf notes, 2020 scribbles, 2020 video, Nowik 2009, Chang Erickson 2017 ]

Planar maps

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

Feb 28
Paper chase assignment due

Planar paths, cuts, and flows

Mar 1
Multiple-source shortest paths
[ html notes, pdf notes, 2020 scribbles, 2020 video, Klein 2005, Chambers Cabello Erickson 2013 ]
Mar 3
Separators and $r$-divisions
[ html notes, pdf notes, 2020 scribbles, 2020 video, Klein Mozes Sommer 2012, Har-Peled Nayyeri 2018 ]
Mar 8
Faster shortest paths, with and without negative edges
[ html notes, pdf notes, 2020 scribbles, 2020 video, Lipton Rose Tarjan 1979, Fakcharoenphol Rao 2006, Klein Mozes Weimann 2009 ]
Mar 10
Minimum cuts
[ html notes, pdf notes, 2020 scribbles, 2020 video, Reif 1983 ]
Mar 18
Undergraduate drop deadline
Mar 13-17
Spring break — No lectures
Mar 22
FR-Dijkstra and faster minimum cuts (finished on Thursday)
[ html notes, pdf notes, 2020 scribbles, 2020 video, Fakcharoenphol Rao 2006, Italiano Nussbaum Sankowski Wulff-Nilsen 2011 ]
Mar 24
Maximum flows
[ updated SODA 2011 slides, 2020 video, Borradaile Klein 2009, Erickson 2010 ]

Surface maps

Mar 29
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, 2020 scribbles, 2020 video ]
Mar 31
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, 2020 scribbles, 2020 video, Gilbert Hutchinson Tarjan 1984, Sppstein 2003 ]
Apr 3
Project proposals due
Apr 5
Overview of submitted project proposals
[ 🔒 all proposals, 🔒 2020 video ]
Apr 7
Homotopy testing (Dehn's algorithm)
[ html notes, pdf notes, 2020 scribbles, 2020 video, Lazarus Rivaud 2012, Erickson Whittlesey 2013 ]
Apr 12
Shortest nontrivial cycles
[ sorry no notes, 2020 scribbles, 2020 video, Erickson Har-Peled 2003, Cabello Chambers Erickson 2013 ]
Apr 14
Minimum cuts and $\mathbb{Z}_2$-homology
[ sorry no notes, 2020 scribbles, 2020 video, Chambers Erickson Nayyeri 2009, Erickson Nayyeri 2011 ]
Apr 14
Graduate drop deadline
Apr 19
Maximum flows and $\mathbb{R}$-homology
[ sorry no notes, 2020 scribbles, 2020 video, Chambers Erickson Nayyeri 2012 ]

Stuff and oddments

Apr 21
Approximation schemes via low-diameter slicing: carvings, branchwidth, dynamic programming, radial greedy tree-cotree decomposition, branchwidth ≤ diameter + 1, slicing
[ sorry no notes, 2020 scribbles, 2020 video, Baker 1994, Eppstein 1999, Demaine Hajiaghayi Mohar 2011 ]
Apr 26
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, 2020 scribbles, 2020 video; Colin de Verdière, Hubard, de Mesmay 2014; Gilbert Hutchinson Tarjan 1984 ]
Apr 28
TBA
May 3
TBA
May 3
Project reports due
May 4
Last day to submit ICES evaluation forms
May 5–11
🔒 Final project presentations

Related topics I didn't have time for in 2019

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

 

Creative Commons License   Powered by MathJax