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
24 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
10 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
18 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
25 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
25 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
43 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
50 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
29 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
30 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
22 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
27 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
23 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
25 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
33 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
60 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
46 plays 0a. Tutte drawings b. Physical intuition: energy minimization c. Halfplane lemma d. No degenerate vertex neighborhoods e. No degenerate faces -
From Jeff Erickson
38 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
48 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
55 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
26 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
43 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
44 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
42 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
51 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
56 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
80 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
244 plays 0a. Definitions of curves, polygons, and simple b. The Jordan Polygon Theorem c. Point-in-polygon algorithm d. Polygons have triangulations