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.
-
From Jeff Erickson
32 plays 0circulations, boundary circulations, real-homology, flow homology basis, feasible boundary circulation iff no negative cycle in dual map, flow homology polytope,… -
From Jeff Erickson
19 plays 0Duality with minimum-weight homologous even subgraph, homology in surfaces with boundary (forest-cotree and tree-cofrest decompositions), Z2-homology cover,… -
From Jeff Erickson
17 plays 0Homology, continued: crossing numbers, cohomology, cosnargles, systems of cocycles, homology annotations Shortest interesting cycles, continued: Sketch of parametric… -
From Jeff Erickson
18 plays 0Homotopy testing continued: universal cover, discrete Gauss-Bonnet, Dehn's lemma, greedy improvement, radial map, system of quads, (spurs and brackets, run-length… -
From Jeff Erickson
24 plays 0Shortest 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)… -
From Jeff Erickson
7 plays 0Menger's theorem, systolic bounds, multicycle separators, depth contours, planarizing subgraphs of size O(sqrt{ng}), separators and r-divisions -
From Jeff Erickson
14 plays 0Homotopy testing, contractibility, reduction to a system of loops, lots of interruptions -
From Jeff Erickson
11 plays 0Cut graphs, homotopy, crossing and traversal paths, spike and face (bigon and vertex) moves, systems of loops, cycle spaces -
From Jeff Erickson
18 plays 0Kerékjártó-Rado theorem, tree-cotree decompositions, systems of loops, handles, twists, Dyck's surface, final classification, Euler characteristic -
From Jeff Erickson
16 plays 02-manifolds, polygonal schemata, cellular embeddings and rotation systems, orientation and genus, band decompositions, reflection systems, deletion and contraction -
From Jeff Erickson
16 plays 0Circulation and flow definitions, boundary circulations, Alexander numbering, feasible circulations dual to shortest paths, max flow by binary search, sketch of O(n log… -
From Jeff Erickson
19 plays 0Shortest paths: Monge arrays, SMAWK, FR-Bellman-Ford Minimum cuts: shortest cycle in dual annulus, MSSP, Reif's divide-and-conquer algorithm -
From Jeff Erickson
20 plays 0Dense distance graphs, generalized nested dissection, sketch of FR-Bellman -
From Jeff Erickson
18 plays 0tree separators, fundamental cycles, level separators, cycle separators, good r-divisions -
From Jeff Erickson
26 plays 0properly shared edges, contraction, distance queries, contraction sharing, total vertices at each level is O(n) -
From Jeff Erickson
26 plays 0shortest paths, slacks, active darts, pivots, disk-tree lemma, dynamic forest data structures -
From Jeff Erickson
31 plays 0...or “Maxwell almost discovered both planar graphs and Voronoi diagrams” — planar frameworks, force diagrams, reciprocal frameworks, polyhedral lifts, -
From Jeff Erickson
13 plays 0Tutte drawings, convex embeddings require 3-connectivity, physical intuition via springs, outer face is outer, halfplanes induce connected subgraphs, no vertex has all… -
From Jeff Erickson
14 plays 0Straight-line planar embedding, star-shaped-hole filling, canonical ordering, Schnyder woods, grid embedding -
From Jeff Erickson
19 plays 0Abstract graphs (darts), topological graphs, data structures, embeddings, maps, rotation systems, duality, derived maps -
From Jeff Erickson
20 plays 0Winding numbers again, Alexander numbering again, smoothing, unsigned Gauss code planarity, parity (Gauss, Nagy), tree-onion figures (Dehn), bipartite interlacement… -
From Jeff Erickson
17 plays 0Immersions, image graphs, homotopy moves, Steinitz's contraction algorithm, $n$ vertices implies $n+2$ faces, signed Gauss codes, Gauss diagrams, tracing faces -
From Jeff Erickson
27 plays 0triangulation, crossing sequences, reduction, the funnel algorithm, holes for free! -
From Jeff Erickson
15 plays 0trapezoidal decomposition, horizontal and vertical ranks, rectification, bracket slides -
From Jeff Erickson
22 plays 0Homotopy testing: crossing sequences, reduction, uniqueness, homotopy invariance again -
From Jeff Erickson
38 plays 0Fast and Loose, non-simple polygon area, winding number definitions, homotopy, (safe) vertex moves, simplicial approximation, homotopy invariance -
From Jeff Erickson
122 plays 0Simple polygons: Jordan polygon theorem, point-in-polygon algorithm, trapezoidal decompositions, polygon triangulations