Search for tag: "topology"

May 3: Maximum flows in surface maps

circulations, boundary circulations, real-homology, flow homology basis, feasible boundary circulation iff no negative cycle in dual map, flow homology polytope, implicit linear programming,…

From  Jeff Erickson 20 plays 0  

Apr 28: minimum cuts

Duality with minimum-weight homologous even subgraph, homology in surfaces with boundary (forest-cotree and tree-cofrest decompositions), Z2-homology cover, minimum-weight homologous cycles (MSSP…

From  Jeff Erickson 13 plays 0  

Apr 26: Homology and short interesting cycles II

Homology, continued: crossing numbers, cohomology, cosnargles, systems of cocycles, homology annotations Shortest interesting cycles, continued: Sketch of parametric MSSP, sketch of recursive…

From  Jeff Erickson 14 plays 0  

Apr 24: Homotopy testing (part 2)

Homotopy testing continued: universal cover, discrete Gauss-Bonnet, Dehn's lemma, greedy improvement, radial map, system of quads, (spurs and brackets, run-length encoding)

From  Jeff Erickson 14 plays 0  

Apr 21: Short interesting cycles and homology (part 1)

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) time Homology: Even subgraphs,…

From  Jeff Erickson 16 plays 0  

Apr 19: Planarizing and separating surface maps

Menger's theorem, systolic bounds, multicycle separators, depth contours, planarizing subgraphs of size O(sqrt{ng}), separators and r-divisions

From  Jeff Erickson 5 plays 0  

Apr 14: Homotopy testing (part 1)

Homotopy testing, contractibility, reduction to a system of loops, lots of interruptions

From  Jeff Erickson 9 plays 0  

Apr 12: Tree-cotree infrastructure 1

Cut graphs, homotopy, crossing and traversal paths, spike and face (bigon and vertex) moves, systems of loops, cycle spaces

From  Jeff Erickson 3 plays 0  

Apr 7: Surface classification

Kerékjártó-Rado theorem, tree-cotree decompositions, systems of loops, handles, twists, Dyck's surface, final classification, Euler characteristic

From  Jeff Erickson 16 plays 0  

Mar 31: Surface maps

2-manifolds, polygonal schemata, cellular embeddings and rotation systems, orientation and genus, band decompositions, reflection systems, deletion and contraction

From  Jeff Erickson 14 plays 0  

Mar 29: Planar circulations and flows

Circulation and flow definitions, boundary circulations, Alexander numbering, feasible circulations dual to shortest paths, max flow by binary search, sketch of O(n log n)-time max-flow via…

From  Jeff Erickson 14 plays 0  

Mar 24: Shortest paths (continued) and minimum cuts

Shortest paths: Monge arrays, SMAWK, FR-Bellman-Ford Minimum cuts: shortest cycle in dual annulus, MSSP, Reif's divide-and-conquer algorithm

From  Jeff Erickson 15 plays 0  

Mar 22: Planar shortest paths

Dense distance graphs, generalized nested dissection, sketch of FR-Bellman

From  Jeff Erickson 16 plays 0  

Mar 10: Separators and r-divisions

tree separators, fundamental cycles, level separators, cycle separators, good r-divisions

From  Jeff Erickson 15 plays 0  

Mar 8: MSSP by recursive contraction

properly shared edges, contraction, distance queries, contraction sharing, total vertices at each level is O(n)

From  Jeff Erickson 22 plays 0  

Mar 1: Multiple-Source Shortest Paths 1

shortest paths, slacks, active darts, pivots, disk-tree lemma, dynamic forest data structures

From  Jeff Erickson 23 plays 0  

Feb 24: Maxwell–Cremona correspondence

...or “Maxwell almost discovered both planar graphs and Voronoi diagrams” — planar frameworks, force diagrams, reciprocal frameworks, polyhedral lifts,

From  Jeff Erickson 23 plays 0  

Feb 22: Tutte’s spring embeddings

Tutte drawings, convex embeddings require 3-connectivity, physical intuition via springs, outer face is outer, halfplanes induce connected subgraphs, no vertex has all neighbors on one line, line…

From  Jeff Erickson 11 plays 0  

Feb 10: Planar graphs and planar maps

Abstract graphs (darts), topological graphs, data structures, embeddings, maps, rotation systems, duality, derived maps

From  Jeff Erickson 17 plays 0  

Feb 8: Unsigned Gauss codes

Winding numbers again, Alexander numbering again, smoothing, unsigned Gauss code planarity, parity (Gauss, Nagy), tree-onion figures (Dehn), bipartite interlacement (Rosensteihl)

From  Jeff Erickson 17 plays 0  

Feb 3: Generic closed curves

Immersions, image graphs, homotopy moves, Steinitz's contraction algorithm, $n$ vertices implies $n+2$ faces, signed Gauss codes, Gauss diagrams, tracing faces

From  Jeff Erickson 16 plays 0  

Feb 1: Shortest homotopic paths

triangulation, crossing sequences, reduction, the funnel algorithm, holes for free!

From  Jeff Erickson 25 plays 0  

Jan 27: Faster homotopy testing

trapezoidal decomposition, horizontal and vertical ranks, rectification, bracket slides

From  Jeff Erickson 14 plays 0  

Jan 25: Multiple obstacles

Homotopy testing: crossing sequences, reduction, uniqueness, homotopy invariance again

From  Jeff Erickson 19 plays 0