CS 598: One-Dimensional Computational Topology (Spring 2023)
CS 598: One-Dimensional Computational Topology (Spring 2023)
See https://jeffe.cs.illinos.edu/teaching/comptop/2023/ for more information about this course.
-
circulations, boundary circulations, real-homology, flow homology basis, feasible boundary circulation iff no negative cycle in dual map, flow homology polytope,…
May 3: Maximum flows in surface maps
From Jeff Erickson
42 plays 0 -
Duality with minimum-weight homologous even subgraph, homology in surfaces with boundary (forest-cotree and tree-cofrest decompositions), Z2-homology cover,…
Apr 28: minimum cuts
From Jeff Erickson
25 plays 0 -
Homology, continued: crossing numbers, cohomology, cosnargles, systems of cocycles, homology annotations Shortest interesting cycles, continued: Sketch of parametric…
Apr 26: Homology and short interesting cycles II
From Jeff Erickson
21 plays 0 -
Homotopy testing continued: universal cover, discrete Gauss-Bonnet, Dehn's lemma, greedy improvement, radial map, system of quads, (spurs and brackets, run-length…
Apr 24: Homotopy testing (part 2)
From Jeff Erickson
20 plays 0 -
Shortest interesting cycles: Contractible vs separating, simplicity, 3-path condition, shortest-path crossing, O(n^3) time, dual cut-graph classification, O(n^2 log n)…
Apr 21: Short interesting cycles and homology…
From Jeff Erickson
25 plays 0 -
Menger's theorem, systolic bounds, multicycle separators, depth contours, planarizing subgraphs of size O(sqrt{ng}), separators and r-divisions
Apr 19: Planarizing and separating surface maps
From Jeff Erickson
11 plays 0 -
Homotopy testing, contractibility, reduction to a system of loops, lots of interruptions
Apr 14: Homotopy testing (part 1)
From Jeff Erickson
15 plays 0 -
Cut graphs, homotopy, crossing and traversal paths, spike and face (bigon and vertex) moves, systems of loops, cycle spaces
Apr 12: Tree-cotree infrastructure 1
From Jeff Erickson
18 plays 0 -
Kerékjártó-Rado theorem, tree-cotree decompositions, systems of loops, handles, twists, Dyck's surface, final classification, Euler characteristic
Apr 7: Surface classification
From Jeff Erickson
26 plays 0 -
2-manifolds, polygonal schemata, cellular embeddings and rotation systems, orientation and genus, band decompositions, reflection systems, deletion and contraction
Mar 31: Surface maps
From Jeff Erickson
24 plays 0 -
Circulation and flow definitions, boundary circulations, Alexander numbering, feasible circulations dual to shortest paths, max flow by binary search, sketch of O(n log…
Mar 29: Planar circulations and flows
From Jeff Erickson
19 plays 0 -
Shortest paths: Monge arrays, SMAWK, FR-Bellman-Ford Minimum cuts: shortest cycle in dual annulus, MSSP, Reif's divide-and-conquer algorithm
Mar 24: Shortest paths (continued) and minimum…
From Jeff Erickson
23 plays 0 -
Dense distance graphs, generalized nested dissection, sketch of FR-Bellman
Mar 22: Planar shortest paths
From Jeff Erickson
22 plays 0 -
tree separators, fundamental cycles, level separators, cycle separators, good r-divisions
Mar 10: Separators and r-divisions
From Jeff Erickson
20 plays 0 -
properly shared edges, contraction, distance queries, contraction sharing, total vertices at each level is O(n)
Mar 8: MSSP by recursive contraction
From Jeff Erickson
27 plays 0 -
shortest paths, slacks, active darts, pivots, disk-tree lemma, dynamic forest data structures
Mar 1: Multiple-Source Shortest Paths 1
From Jeff Erickson
31 plays 0 -
...or “Maxwell almost discovered both planar graphs and Voronoi diagrams” — planar frameworks, force diagrams, reciprocal frameworks, polyhedral lifts,
Feb 24: Maxwell–Cremona correspondence
From Jeff Erickson
57 plays 0 -
Tutte drawings, convex embeddings require 3-connectivity, physical intuition via springs, outer face is outer, halfplanes induce connected subgraphs, no vertex has all…
Feb 22: Tutte’s spring embeddings
From Jeff Erickson
23 plays 0 -
Straight-line planar embedding, star-shaped-hole filling, canonical ordering, Schnyder woods, grid embedding
Feb 17: Straight-line Planar Maps
From Jeff Erickson
17 plays 0 -
Abstract graphs (darts), topological graphs, data structures, embeddings, maps, rotation systems, duality, derived maps
Feb 10: Planar graphs and planar maps
From Jeff Erickson
31 plays 0 -
Winding numbers again, Alexander numbering again, smoothing, unsigned Gauss code planarity, parity (Gauss, Nagy), tree-onion figures (Dehn), bipartite interlacement…
Feb 8: Unsigned Gauss codes
From Jeff Erickson
23 plays 0 -
Immersions, image graphs, homotopy moves, Steinitz's contraction algorithm, $n$ vertices implies $n+2$ faces, signed Gauss codes, Gauss diagrams, tracing faces
Feb 3: Generic closed curves
From Jeff Erickson
23 plays 0 -
triangulation, crossing sequences, reduction, the funnel algorithm, holes for free!
Feb 1: Shortest homotopic paths
From Jeff Erickson
34 plays 0 -
trapezoidal decomposition, horizontal and vertical ranks, rectification, bracket slides
Jan 27: Faster homotopy testing
From Jeff Erickson
17 plays 0 -
Homotopy testing: crossing sequences, reduction, uniqueness, homotopy invariance again
Jan 25: Multiple obstacles
From Jeff Erickson
29 plays 0 -
Fast and Loose, non-simple polygon area, winding number definitions, homotopy, (safe) vertex moves, simplicial approximation, homotopy invariance
Jan 20: Winding numbers, homotopy
From Jeff Erickson
53 plays 0 -
Simple polygons: Jordan polygon theorem, point-in-polygon algorithm, trapezoidal decompositions, polygon triangulations
Jan 18: Introduction, Jordan polygon theorem
From Jeff Erickson
164 plays 0
Search for ""