Search for tag: "topology"

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

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…

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

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

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,…

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

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

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

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

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

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…

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

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

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

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

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

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

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…

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

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

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

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

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

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