# 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, especially in the last section. 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, Steinitz's contraction algorithm, $n$ vertices implies $n+2$ faces, signed Gauss codes, Gauss diagrams, tracing faces
[ html notes, pdf notes, html notes 2, pdf notes 2, scribbles, video, Carter 1991 ]
[ 2020 scribbles, 2020 video, 2020 scribbles 2, 2020 video 2 ]
Feb 8
Winding numbers again, Alexander numbering again, smoothing, unsigned Gauss code planarity, parity (Gauss, Nagy), tree-onion figures (Dehn), bipartite interlacement (Rosensteihl)
[ html notes, pdf notes, scribbles, video ]
[ 2020 scribbles, 2020 video ]

### Planar maps

Feb 10
Abstract graphs (darts), topological graphs, data structures, embeddings, maps, rotation systems, duality, derived maps
[ html notes, pdf notes, scribbles, video ]
[ 2020 scribbles, 2020 video ]
Feb 15
Deletion and contraction, tree-cotree decomposition, Euler's formula, discrete Gauss-Bonnet formula
[ html notes, pdf notes, scribbles, sorry no video ]
[ 2020 scribbles, 2020 video ]
Feb 17
Straight-line embedding, star-shaped-hole filling, canonical ordering, Schnyder woods, grid embedding
[ html notes, pdf notes, scribbles, video, De Fraysseix Pach Pollack 1990, Schnyder 1990 ]
[ 2020 scribbles, 2020 video, ]
Feb 22
Equilibrium stresses, Tutte's spring embedding, polyhedral embeddings
[ html notes, pdf notes, scribbles, video Tutte 1963, Floater 1997, Spielman 2018 ]
[ 2020 scribbles, 2020 video, ]
Feb 24
🆕 The Maxwell–Cremona correspondence: planar frameworks, reciprocal frameworks, polyhedral lifts
[ scribbles, video, html notes, pdf notes ]
Feb 28
Paper chase assignment due

### Planar paths, cuts, and flows

Mar 1
Parametric multiple-source shortest paths: shortest paths, slacks, active darts, pivots, disk-tree lemma, dynamic forest data structures
[ html notes, pdf notes, scribbles, video, Klein 2005, Cabello Chambers Erickson 2013 ]
[ 2020 scribbles, 2020 video, ]
Mar 3
Class cancelled; Jeff was sick
Mar 8
🆕 Recursive multiple-source shortest paths
[ html notes, pdf notes, Das, Kipouridis, Probst-Gutenberg, Wulff-Nilsen 2022 ]
Mar 10
Separators and $r$-divisions
[ html notes, pdf notes, 2020 scribbles, 2020 video, Klein Mozes Sommer 2012, Har-Peled Nayyeri 2018 ]
Mar 18
Mar 13-17
Spring break — No lectures
Mar 22
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 24
Minimum cuts
[ html notes, pdf notes, 2020 scribbles, 2020 video, Reif 1983 ]
Skip?
FR-Dijkstra and faster minimum cuts
[ html notes, pdf notes, 2020 scribbles, 2020 video, Fakcharoenphol Rao 2006, Italiano Nussbaum Sankowski Wulff-Nilsen 2011 ]
Mar 29
Maximum flows
[ updated SODA 2011 slides, 2020 video, Borradaile Klein 2009, Erickson 2010 ]

### Surface maps

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

### Miscellanea

Apr 26
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 28
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 ]
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.
• Polygons: weakly simple polygons [Meister, Minc, Skopenkov, ...], Fréchet distance [Alt Godau], mountain climbing [Homma, Huneke], linkages and rigidity, Carpenter's rule theorem [Connelly Demaine Rote, Streinu]
• Topological combinatorial geometry: Jordan curve theorem via Hex/Y, pseudoline arrangements, order types [Goodman Pollack], stretchability and universality [Mnëv, Shor, ...], $\exists\mathbb{R}$-completeness
• Generic curves: self-overlapping curves, homotopy area
• Planar map structures: Forbidden minors [Kuratowski, Wagner], Steinitz's theorem (Tutte-Maxwell or via medial curve simplification), Alexandrov's theorem, Koebe-Andreev-Thurston circle-packing, squared rectangles [Dudeney, Dehn, Brooks Tutte, ...], electrical reduction [Kennelly, Steinitz, Feo Provan, Truemper, ...], Hanani-Tutte theorem, Okamura-Seymour theorem, crossing lemmas [Ajtai Chvátal Newborn Szemerédi Leighton], rigidity, pseudo-triangulations, the carpenter's rule, string graphs, distributive flow lattices [Khuller Naor Klein], flip graphs
• Planar graph algorithms: enumeration/random sampling [Tutte], planarity testing, morphing [Steinitz Rademacher, Cairns], maximum cut $\leftrightharpoons$ Chinese postman [Hadlock], planar graph isomorphism [Weinberg Hopcroft Tarjan Wong], planar network simplex, spanners, approximate distance oracles, Gomory-Hu trees, multi-terminal maximum flow, subquadratic diameter, weak embeddings, clustered planarity, branchwidth (and other width parameters), approximation via local search [Mattieu], appromimation via brick decomposition [Klein, Demaine, inter alia], contour trees, terrain simplification, homotopy height
• Surface map structures: Discrete differential geometry (an entire course), graph minor theory [Robertson Seymour] (an entire course), toroidal geodesic/periodic planar embeddings, geodesic spring embedding [Colin de Verdière oncle], circle packing [Thurston, Colin de Verdière oncle, Mohar], shortest-path embeddings, systolic inequalities, holiest paths and flows, toroidal Maxwell-Cremona [Erickson Lin]
• Surface map algorithms: Canonicalizing systems of loops [Dehn, Brahana], Reeb graphs, mesh simplification, genus approximation [Sidiropoulos et al.], curve tracing [Erickson Nayyeri, Bell], isotopy testing [Colin de Verdière neveu, De Mesmay], shortest homotopic paths [Colin de Verdière neveu, Lazarus, Erickson], optimal cycle bases, optimal homology bases, Gomory-Hu trees, homotopy area [Chambers Wang], more approximation algorithms (an entire course), persistent homology (an entire course)