CS 598 JGE — Computational Topology — Fall 2020
CS 598 JGE — Computational Topology — Fall 2020
All videos in this channel are licensed under a Creative Commons Attribution 4.0 license.
-
From Jeff Erickson on 12/8/2020
12 plays 0a. The puppy problem b. Special cases: blind vs. stubborn, puppies vs. guppies c. Configurations and the puppy diagram (Look, actual code!) d. Counting essential… -
From Jeff Erickson on 12/3/2020
4 plays 0a. Shortest non-separating cycles b. Menger's theorem c. Planarizing with at most g cycles via cycles: O(sqrt{gn} log g) d. Greedy tree-cotree again again e.… -
From Jeff Erickson on 12/1/2020
4 plays 0a. Carvings b. Branch decompositions c. Dynamic programming c. Radial and medial maps d. Radial greedy tree-cotree decomposition e. Branchwidth ≤ diameter ≠ 1 f.… -
From Jeff Erickson on 11/19/2020
10 plays 0a. 1-chains = pseudoflows, circulations b. 2-chains = face potentials = Alexander numberings, boundary circulations c. Real-homology d. cycles, cocycles, and homology… -
From Jeff Erickson on 11/17/2020
7 plays 0a. Even subgraphs, cycle space, edge cuts, and cut spaceb. Planar duality c. Boundary subgraphs d. Z2-homology e. Systems of cycles and cocycles f. Homology anotations… -
From Jeff Erickson on 11/12/2020
12 plays 0a. Planarization b. Contractible versus separating c. Thomassen's 3-path condition ⇒ O(n³) time d. Greedy tree-cotree decompositions e. Greedy (reduced)… -
From Jeff Erickson on 11/10/2020
15 plays 0a. Modeling curves on surfaces as walks in maps b. Spur and face moves c. System of loops d. Contractible in surface = closed in universal cover e. Dehn's lemma f.… -
From Jeff Erickson on 10/29/2020
11 plays 0a. Kerékjártó-Rado theorem (Every surface supports a map.) b. Tree-cotree decompositions and systems of loops c. Detaching handles by contracting… -
From Jeff Erickson on 10/27/2020
5 plays 0a. 2-manifolds b. Polygonal schemata c. Cellular embeddings and rotation systems d. Orientation and genus e. Band decompositions f. Reflection systems g. Deletion and… -
From Jeff Erickson on 10/22/2020
8 plays 0a. FR-Dijkstra summary b. O(n log log n) minimum cut overview c. Technical details d. Planar maximum flow history e. Venkatesan's duality between flows and… -
From Jeff Erickson on 10/20/2020
12 plays 0a. Monge heap operations: Revealing columns and hiding rows b. Range minimum queries c. Monge heap implementation d. High-level overview of FR-Dijkstra e. Monge… -
From Jeff Erickson on 10/15/2020
13 plays 0a. Duality: Shortest essential cycle b. Crosses shortest path at most once c. Slicing into a shortest-path problem d. Easy algorithms: Brute force and MSSP e.… -
From Jeff Erickson on 10/13/2020
7 plays 0a. Dense distance graphs b. Improving Dijkstra to O(n log log n) time c. Repricing d. Nested dissection e. Monge arrays and SMAWK f. Planar distances are (almost) Monge)… -
From Jeff Erickson on 10/8/2020
11 plays 0a. Tree separators b. Fundamental cycle separators c. BFS level separators d. Face-level cycles e. Short cycle separators f. Good r-divisions -
From Jeff Erickson on 10/6/2020
15 plays 0a. Problem statement b. Shortest paths and slacks c. Disk-tree lemma and compact output d. Red and blue vertices, active darts e. Dynamic forest data structures f.… -
From Jeff Erickson on 10/1/2020
12 plays 0a. Tutte drawings b. Physical intuition: energy minimization c. Halfplane lemma d. No degenerate vertex neighborhoods e. No degenerate faces -
From Jeff Erickson on 09/29/2020
12 plays 0a. Simple triangulation lemma b. Hole filling (Every pentagon is star-shaped) c. Vertex deletion d. Schnyder woods e. Grid embedding -
From Jeff Erickson on 09/24/2020
14 plays 0a. Deletion and contraction in abstract graphs b. Spanning trees c. Planar duality: (Σ\e)* = Σ*/e* d. Implementing deletion and contraction in maps e.… -
From Jeff Erickson on 09/22/2020
27 plays 0a. What is a graph? (vertices and darts) b. Incidence list and incidence array data structures c. Planar maps: faces, shores, face degree d. Rotation systems e.… -
From Jeff Erickson on 09/17/2020
10 plays 0a. Steinitz's contraction algorithm (spindle removal) b. Rotation number: Smiles minus frowns c. Rotation number: Initial winding and writhe d. Defect -
From Jeff Erickson on 09/15/2020
23 plays 0a. Winding numbers and Alexander numbering b. Gauss smoothing and Seifert decompositions c. Gauss' parity condition and the Nagy graph d. Dehn smoothing and Euler… -
From Jeff Erickson on 09/10/2020
20 plays 0a. Definitions: transverse intersection, generic curve (immersion) b. Isotopy c. Image graphs and their faces d. Homotopy moves e. Planarity: F = V+2 f. Gauss codes and… -
From Jeff Erickson on 09/8/2020
24 plays 0a. Shortest paths in simple polygons b. Crossing sequences via triangulation c. Dual tree of a polygon triangulation d. The funnel algorithm e. Adding holes: Nothing… -
From Jeff Erickson on 09/3/2020
31 plays 0a. Quadratic lower bound? b. Trapezoidal decomposition c. Bentley-Ottmann sweep-line algorithm d. Horizontal and vertical ranks e. Rectification f. Sliding brackets g.… -
From Jeff Erickson on 09/1/2020
29 plays 0a. Crossing sequences b. Same crossing sequence implies homotopy (but not vice versa) c. Elementary reductions and expansions d. Uniqueness of reduction e. Homotopic iff… -
From Jeff Erickson on 08/27/2020
42 plays 0a. Fast and Loose b. Signed polygon area c. Winding number definitions d. Homotopy definitions (for the once-punctured plane) e. Safe vertex moves (for the… -
From Jeff Erickson on 08/25/2020
140 plays 0a. Definitions of curves, polygons, and simple b. The Jordan Polygon Theorem c. Point-in-polygon algorithm d. Polygons have triangulations
