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
13 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
6 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
5 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
11 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
8 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
13 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
18 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
14 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
12 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
11 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
16 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
15 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
10 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
18 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
22 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
21 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
21 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
18 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
36 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
14 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
27 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
26 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
27 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
35 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
33 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
51 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
167 plays 0a. Definitions of curves, polygons, and simple b. The Jordan Polygon Theorem c. Point-in-polygon algorithm d. Polygons have triangulations
