CS 598: One-Dimensional Computational Topology (Spring 2023)
CS 598: One-Dimensional Computational Topology (Spring 2023)
-
From Jeff Erickson
2 plays 0tree separators, fundamental cycles, level separators, cycle separators, good r-divisions -
From Jeff Erickson
3 plays 0properly shared edges, contraction, distance queries, contraction sharing, total vertices at each level is O(n) -
From Jeff Erickson
8 plays 0shortest paths, slacks, active darts, pivots, disk-tree lemma, dynamic forest data structures -
From Jeff Erickson
2 plays 0...or “Maxwell almost discovered both planar graphs and Voronoi diagrams” — planar frameworks, force diagrams, reciprocal frameworks, polyhedral lifts, -
From Jeff Erickson
4 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
5 plays 0Straight-line planar embedding, star-shaped-hole filling, canonical ordering, Schnyder woods, grid embedding -
From Jeff Erickson
6 plays 0Abstract graphs (darts), topological graphs, data structures, embeddings, maps, rotation systems, duality, derived maps -
From Jeff Erickson
9 plays 0Winding numbers again, Alexander numbering again, smoothing, unsigned Gauss code planarity, parity (Gauss, Nagy), tree-onion figures (Dehn), bipartite interlacement… -
From Jeff Erickson
3 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
9 plays 0triangulation, crossing sequences, reduction, the funnel algorithm, holes for free! -
From Jeff Erickson
6 plays 0trapezoidal decomposition, horizontal and vertical ranks, rectification, bracket slides -
From Jeff Erickson
7 plays 0Homotopy testing: crossing sequences, reduction, uniqueness, homotopy invariance again -
From Jeff Erickson
14 plays 0Fast and Loose, non-simple polygon area, winding number definitions, homotopy, (safe) vertex moves, simplicial approximation, homotopy invariance -
From Jeff Erickson
26 plays 0Simple polygons: Jordan polygon theorem, point-in-polygon algorithm, trapezoidal decompositions, polygon triangulations
