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.
-
a. The puppy problem b. Special cases: blind vs. stubborn, puppies vs. guppies c. Configurations and the puppy diagram (Look, actual code!) d. Counting essential…
∞. Chasing puppies
From Jeff Erickson
25 plays 0 -
a. 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.…
26. Planarizing and separating surface maps
From Jeff Erickson
10 plays 0 -
a. Carvings b. Branch decompositions c. Dynamic programming c. Radial and medial maps d. Radial greedy tree-cotree decomposition e. Branchwidth ≤ diameter ≠ 1 f.…
25. Approximation schemes via slicing
From Jeff Erickson
19 plays 0 -
a. 1-chains = pseudoflows, circulations b. 2-chains = face potentials = Alexander numberings, boundary circulations c. Real-homology d. cycles, cocycles, and homology…
24. Maximum flows in surface maps
From Jeff Erickson
27 plays 0 -
a. 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…
23. Minimum cuts in surface maps
From Jeff Erickson
29 plays 0 -
a. Planarization b. Contractible versus separating c. Thomassen's 3-path condition ⇒ O(n³) time d. Greedy tree-cotree decompositions e. Greedy (reduced)…
22. Shortest nontrivial cycles in surfaces
From Jeff Erickson
45 plays 0 -
a. 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.…
21. Homotopy testing on surfaces
From Jeff Erickson
52 plays 0 -
a. Kerékjártó-Rado theorem (Every surface supports a map.) b. Tree-cotree decompositions and systems of loops c. Detaching handles by contracting…
20. Surface Classification
From Jeff Erickson
33 plays 0 -
a. 2-manifolds b. Polygonal schemata c. Cellular embeddings and rotation systems d. Orientation and genus e. Band decompositions f. Reflection systems g. Deletion and…
19. Surface Maps
From Jeff Erickson
31 plays 0 -
a. 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…
18. Faster minimum cuts and maximum flows
From Jeff Erickson
25 plays 0 -
a. 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…
17. FR-Dijkstra and faster minimum cuts
From Jeff Erickson
30 plays 0 -
a. 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.…
16. Planar minimum cuts
From Jeff Erickson
24 plays 0 -
a. 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)…
15. Planar shortest paths
From Jeff Erickson
26 plays 0 -
a. Tree separators b. Fundamental cycle separators c. BFS level separators d. Face-level cycles e. Short cycle separators f. Good r-divisions
14. Planar separators
From Jeff Erickson
36 plays 0 -
a. 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.…
13. Multiple-source shortest paths
From Jeff Erickson
62 plays 0 -
a. Tutte drawings b. Physical intuition: energy minimization c. Halfplane lemma d. No degenerate vertex neighborhoods e. No degenerate faces
12. Tutte's spring embedding
From Jeff Erickson
48 plays 0 -
a. Simple triangulation lemma b. Hole filling (Every pentagon is star-shaped) c. Vertex deletion d. Schnyder woods e. Grid embedding
11. Straight-line planar maps
From Jeff Erickson
40 plays 0 -
a. Deletion and contraction in abstract graphs b. Spanning trees c. Planar duality: (Σ\e)* = Σ*/e* d. Implementing deletion and contraction in maps e.…
10. Deletion and contraction
From Jeff Erickson
52 plays 0 -
a. 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.…
9. Planar graphs and maps
From Jeff Erickson
57 plays 0 -
a. Steinitz's contraction algorithm (spindle removal) b. Rotation number: Smiles minus frowns c. Rotation number: Initial winding and writhe d. Defect
8. Curve homotopy and curve invariants
From Jeff Erickson
27 plays 0 -
a. Winding numbers and Alexander numbering b. Gauss smoothing and Seifert decompositions c. Gauss' parity condition and the Nagy graph d. Dehn smoothing and Euler…
7. Unsigned Gauss codes
From Jeff Erickson
44 plays 0 -
a. 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…
6. Generic curves in the plane
From Jeff Erickson
46 plays 0 -
a. 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…
5. Shortest homotopic paths
From Jeff Erickson
42 plays 0 -
a. Quadratic lower bound? b. Trapezoidal decomposition c. Bentley-Ottmann sweep-line algorithm d. Horizontal and vertical ranks e. Rectification f. Sliding brackets g.…
4. Faster homotopy testing
From Jeff Erickson
52 plays 0 -
a. Crossing sequences b. Same crossing sequence implies homotopy (but not vice versa) c. Elementary reductions and expansions d. Uniqueness of reduction e. Homotopic iff…
3. Homotopy testing with more obstacles
From Jeff Erickson
57 plays 0 -
a. 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…
2. Winding numbers and homotopy
From Jeff Erickson
82 plays 0 -
a. Definitions of curves, polygons, and simple b. The Jordan Polygon Theorem c. Point-in-polygon algorithm d. Polygons have triangulations
1. Simple polygons
From Jeff Erickson
259 plays 0
Search for ""