Search for tag: "topology"

May 3: Maximum flows in surface maps

circulations, boundary circulations,…

From  Jeff Erickson 37 plays 0  

Apr 28: minimum cuts

Duality with minimum-weight homologous even…

From  Jeff Erickson 21 plays 0  

Apr 26: Homology and short interesting cycles II

Homology, continued: crossing numbers,…

From  Jeff Erickson 20 plays 0  

Apr 24: Homotopy testing (part 2)

Homotopy testing continued: universal cover,…

From  Jeff Erickson 19 plays 0  

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

Shortest interesting cycles: Contractible vs…

From  Jeff Erickson 24 plays 0  

Apr 19: Planarizing and separating surface maps

Menger's theorem, systolic bounds,…

From  Jeff Erickson 8 plays 0  

Apr 14: Homotopy testing (part 1)

Homotopy testing, contractibility, reduction to a…

From  Jeff Erickson 14 plays 0  

Apr 12: Tree-cotree infrastructure 1

Cut graphs, homotopy, crossing and traversal…

From  Jeff Erickson 14 plays 0  

Apr 7: Surface classification

Kerékjártó-Rado theorem, tree-cotree…

From  Jeff Erickson 22 plays 0  

Mar 31: Surface maps

2-manifolds, polygonal schemata, cellular…

From  Jeff Erickson 20 plays 0  

Mar 29: Planar circulations and flows

Circulation and flow definitions, boundary…

From  Jeff Erickson 16 plays 0  

Mar 24: Shortest paths (continued) and minimum cuts

Shortest paths: Monge arrays, SMAWK,…

From  Jeff Erickson 19 plays 0  

Mar 22: Planar shortest paths

Dense distance graphs, generalized nested…

From  Jeff Erickson 20 plays 0  

Mar 10: Separators and r-divisions

tree separators, fundamental cycles, level…

From  Jeff Erickson 19 plays 0  

Mar 8: MSSP by recursive contraction

properly shared edges, contraction, distance…

From  Jeff Erickson 26 plays 0  

Mar 1: Multiple-Source Shortest Paths 1

shortest paths, slacks, active darts, pivots,…

From  Jeff Erickson 28 plays 0  

Feb 24: Maxwell–Cremona correspondence

...or “Maxwell almost discovered both…

From  Jeff Erickson 48 plays 0  

Feb 22: Tutte’s spring embeddings

Tutte drawings, convex embeddings require…

From  Jeff Erickson 19 plays 0  

Feb 10: Planar graphs and planar maps

Abstract graphs (darts), topological graphs, data…

From  Jeff Erickson 25 plays 0  

Feb 8: Unsigned Gauss codes

Winding numbers again, Alexander numbering again,…

From  Jeff Erickson 21 plays 0  

Feb 3: Generic closed curves

Immersions, image graphs, homotopy moves,…

From  Jeff Erickson 19 plays 0  

Feb 1: Shortest homotopic paths

triangulation, crossing sequences, reduction, the…

From  Jeff Erickson 30 plays 0  

Jan 27: Faster homotopy testing

trapezoidal decomposition, horizontal and…

From  Jeff Erickson 15 plays 0  

Jan 25: Multiple obstacles

Homotopy testing: crossing sequences, reduction,…

From  Jeff Erickson 28 plays 0