CS 598: Computational Topology (Fall 2009)

   About    Schedule    References    Coursework    Projects   


Future dates are approximate, and future lecture topics are subject to change. (In particular, some topics slated for a single lecture may take more than one; others may be dropped due to lack of time.) Some keywords are links to relevant articles in Wikipedia. Key references for each lecture are highlighted. Other references contain related material (such as historical references or later improvements and extensions) that I may cover in class only briefly or not at all.

Lecture notes are available for some topics—look for links in the left margin. Most of these notes are sketchy; most (if not all) of them are also buggy. Feedback is welcome, especially if you find mistakes!

   Introduction    Paths in the plane    Curves on surfaces   
   Topological graph theory    Normal curves and surfaces    Homology   

   This week's lecture    Future Topics    Related Topics   


Tue, Aug 25
no notes

The Seven Bridges of Königsberg and two other bridge systems.
From Euler [Commentarii 1735]

Introduction, history, overview, and administrivia.

Paths in the plane

Thu, Aug 27

A simple polygon.
from Kaplan and Bosch [BRIDGES 2005]

The Jordan-Schönflies Theorem, testing whether a point lies inside a polygon

Tue, Sep 1

A path in a planar region and a lift to the universal cover.
From Gao et al. [SOCG 1998]

Path homotopy, contractible, simply connected, covering space, universal cover
Shortest homotopic paths: triangulation, crossing sequences, reduction, sleeve, funnel

Thu, Sep 3
Tue, Sep 8

Reduction from Hopcroft's problem to contractibility.
From Cabello et al. [DCG 2004]

Testing homotopy between paths in the punctured plane: sentinel points, monotone paths, vertical ranking, rectified paths, sliding brackets

Thu, Sep 10

A buffer of hexahedra around a subdivided tetrahedral mesh.
From Eppstein [CGTA 1999]

Regular homotopy, winding and turning numbers, the Whitney-Graustein theorem, hexahedral meshing, cube complexes for balls

Curves on Surfaces

Tue, Sep 15
HW 1 released

Eric Testroete's papercraft self-portrait (2009)
combinatorial 2-manifolds, polygonal schemas, rotation systems, barycentric subdivision, duality, equivalence with topological 2-manifolds
Thu, Sep 17

Dyck's surface Σ(1,1)=Σ(0,3).
adapted from Dyck
[Math. Ann. 1888]
surface classification, attaching handles and Möbius bands, contracting and deleting edges, tree-cotree decomposition, system of loops, “Oilers' formula”

Tue, Sep 22
Thu, Sep 24

The Cayley graph of the fundamental group of the double torus.
From Yann Oliver
fundamental groups, group presentations, one-relator presentation from any system of loops, universal covers, hyperbolic tilings, Dehn's contractibility algorithm, compressed crossing sequences

Tue, Sep 29
Thu, Oct 1

The shortest splitting cycle can cross a shortest path Ω(g) times.
From Chambers et al.
[CGTA 2008]
shortest non-contractible cycles, three-path condition, modified Dijkstra, crossing shortest paths, cutting into disks, cut graphs, crossing sequences

Tue, Oct 6
Thu, Oct 8
no notes
(see paper)

Two cycles on a double-torus.
From Chambers et al.
[SoCG 2009]
minimum cuts in surface graphs: boundary subgraphs, ℤ₂-homology, shortest-path crossing bounds, crossing (parity) vectors, weighted triangulations

Topological graph theory

Tue, Oct 13
Thu, Oct 15
HW2 released

A small balanced separator of a planar graph.
From Ken Stephenson
graph separators: Menger's theorem, planar graphs, disk packing, center points, greedy tree-cotree decomposition, level slicing

Tue, Oct 20

A tree decomposition for a planar triangulation.
From Eppstein [JGAA 1999]
tree decompositions, treewidth, Baker's slicing technique, treewidth vs. diameter, PTAS for maximum independent set

Thu, Oct 22

Interlaced parallel bundles.
From Vollmerhaus 1987
Graph minors: definitions, Kuratowski-Wagner, examples, the Graph Minor Theorem, minor-closed families, finite obstruction sets, membership algorithm, combinatorial properties, planar minor or bounded treewidth, decomposition theorem, lots of references but no proofs

Normal curves and surfaces

Tue, Oct 27
Thu, Oct 29

Representatives of two isotopy classes of curves.
From Schaefer et al.
[CCCG 2008]
Normal curves, corner and edge coordinates, exponential compression, straight-line programs, word equations, testing connectivity, counting components, testing isotopy
Tue, Nov 4

Wolfgang Haken's “Gordian unknot”
From Ian Agol
Normal surfaces, knots, ambient isotopy, spanning disk, triangulating knot manifolds, Haken normal cone, fundamental surfaces, vertex surfaces, unknot ∈ NP

Project proposals

Thu, Nov 6

Light cycles from Tron (1982)
Problem summary presentations — no regular lecture

Complexes and Homology

Tue, Nov 9

From Jonathan Puckey's ”Delaunay Raster“ series (2009)
Cell complex definitions: abstract simplicial complexes, geometric simplicial complexes, polytopal complexes, cubical complexes, Δ-complexes, Closure-finite Weak-topology (CW) complexes
Thu, Nov 11

A three-round test-and-set protocol complex
from Herlihy and Rajsbaum (1995)
Cell complex examples: Alexandroff-Čech complexes, Vietoris-Rips complexes, Delaunay complexes, alpha complexes; state/configuration complexes; monotone graph property complexes; presentation complexes and undecidability
Tue, Nov 16
Thu, Nov 18

A first homology basis
from Dey et al. [SIGGRAPH 2008]
Simplicial homology: chains, boundary homomorphisms, cycles, boundaries, homology classes, homology groups, Euler-Poincaré formula, invariance and the Hauptvermutung, homology of 2-manifolds from polygonal schemata, the Smith-Poincaré reduction algorithm
Tue, Nov 23
Thu, Nov 25
Thanksgiving break
no classes!
Tue, Dec 1
[no notes yet]

A topological bar code. Get it?
From Rob Ghrist
Persistent homology: motivation (robust topological inference), images of maps between homology groups induced by inclusion, filtrations, positive and negative simplices, incremental computation, simplex pairing, persistence barcodes/diagrams, extracting persistent homology groups, time-based persistence
Thu, Dec 3
[no notes; see paper]

Five streets.
The paper Amir and I submitted to SOCG yesterday, which has nothing to do with homology but I'm very tired and the voices in my head won't let me think about anything abelian woah is that a wombat?
Tue, Dec 8
[no notes yet]

A commutative diagram
from Cohen-Steiner et al. [DCG 2007]
Persistent homology continued: persistence modules, graded ℤ₂[t]-module decompositions (via Smith-Poincaré reduction), barcodes/diagrams revisited, tame functions, sublevel sets, barcodes/diagrams rerevisited, Hausdorff and bottleneck distance between point multisets, hey look an actual commutative diagram, quadrants and boxes, stability of persistence diagrams

Final Project Presentations

Wed Dec 16
Thu Dec 17

Nested Klein bottles,
by Alan Bennett (1995)
Final project presentations

Related Topics

These are topics that are definitely within the scope of the class, but that I do not plan to did not cover this semester. This is an incredibly incomplete list; please don't be insulted if your favorite result is missing! I expect to cover a very different set of material the next time I teach this class.

A point set, its unit-distance graph, its Vietoris-Rips complex, and its shadow.
From Chambers et al.
[SOCG 2008]
Vietoris-Rips complexes and sensor coverage
Surface encoding and compression: Edgebreaker, Schneyder woods
Knot and link invariants: crossing number, bridge number, twist, writhe, genus, Alexander-Conway, Jones, Homflypt/Flypmoth/Thomflyp/skein
Discrete Morse theory, Reeb graphs, Morse-Smale complexes, harmonic quadrangulation
Friedman's homology through combinatorial Laplacians
Zig-zag homology
Maximum flows on surface-embedded graphs