CS/SE 7301.003.20F — Recent Advances in Computing — Computational Topology

Fall 2020
Mondays and Wednesdays 1:00pm–2:15pm
Live lectures: MS Teams. Link will be given in the "CS 7301.003 2208" team.
Recorded lectures: Posted in the Lectures channel of the "CS 7301.003 2208" team as soon as they are available.


Kyle Fox
Office: ECSS 4.224 (all meetings will likely be online)
Phone: (972) 883-4168
Email: kyle.fox@utdallas.edu
Office Hours: Wednesdays 2:30pm–3:30pm and Thursdays 10:30am–11:30am via MS Teams (tentative). Additional or private office hours available by request. Please email Kyle directly.
Homepage: https://personal.utdallas.edu/~kyle.fox/


About this course
About course projects
Writing policies and advice
Course syllabus: (MS Word) (pdf)


Schedule and Homework

The schedule below will be updated with new subjects and recommended readings throughout the semester. Exact topics discussed in each lecture may change.

Shortly before or after each lecture, I will update the readings with my own notes/script. Use at your own risk! My notes likely have typos or maybe even a few bugs!

The notes from the first seven lectures contain content and figures from computational topology courses by Jeff Erickson.

Date Subject/Event Reading Notes
Mon, Aug. 17th Administrivia, curves in the plane, Jordan curve theorem Erickson 1; lecture notes
Wed, Aug. 19th Triangulations, Jordan-Schönflies Theorem Erickson 1; lecture notes
Mon, Aug. 24th Abstract graphs, planar graphs and rotation systems, and duality Erickson 2; lecture notes Prerequesite form due (instructions)
Wed, Aug. 26th Primal-dual correspondences, Euler's formula Erickson 2; lecture notes
Mon, Aug. 31st Minimum spanning trees in planar graphs, straight-line embeddings via Schnyder Woods Erickson 2; lecture notes
Wed, Sept. 2nd Path and cycle homotopy Erickson 3; lecture notes
Mon, Sept. 7th No class; university closed for Labor Day
Wed, Sept. 9th Homotopy testing Erickson 3; lecture notes
Mon, Sept. 14th Planar graph separators Klein and Mozes 5; Har-Peled and Nayyeri; Erickson scribbles; lecture notes
Wed, Sept. 16th Minimum s,t-cuts in planar graphs Erickson scribbles; lecture notes Homework 1 due Friday, September 18th (LaTeX source) (solutions template) (solutions)
Mon, Sept. 21st Multiple-source shortest paths Klein and Mozes 7; Erickson scribbles; lecture notes
Wed, Sept. 23rd Maximum flow in planar graphs Klein and Mozes 10; Erickson scribbles; Erickson paper; lecture notes
Mon, Sept. 28th Finish maximum flows Klein and Mozes 7; Erickson scribbles; lecture notes
Wed, Sept. 30th Surface maps Erickson map scribbles; Erickson notes; lecture notes
Mon, Oct. 5th Non-orientable surfaces and boundary Erickson map scribbles; More Erickson scribbles; Erickson notes; Tree-coforest and forest-cotree decompositions (Section 3); lecture notes
Wed, Oct. 7th Shortest non-trivial cycles Erickson scribbles; in \(n \log \log n\) time (Section 3); lecture notes Homework 2 due Friday, October 9th (LaTeX source) (solutions)
Mon, Oct. 12th Minimum s,t-cuts in surface graphs Erickson scribbles; minimum cuts paper; alternative signature proofs (Section 3); lecture notes
Wed, Oct. 14th More minimum cuts in surface graphs minimum cuts paper; lecture notes
Mon, Oct. 19th Graph minors Erickson notes; lecture notes
Wed, Oct. 21st Algorithms exploiting low treewidth Erickson notes; lecture notes Project proposals due Friday, October 23rd
Mon, Oct. 26th Cell complex definitions Erickson notes; Edelsbrunner notes; lecture notes
Wed, Oct. 28th Cell complex examples Erickson notes; Edelsbrunner notes on AC and VR complexes, Delaunay complexes, and alpha complexes, lecture notes
Mon, Nov. 2nd Simplicial homology definitions Erickson notes; lecture notes
Wed, Nov. 4th Euler-Poincaré formula, reduction algorithm for computing homology Erickson notes (see the warning in my notes); lecture notes
Mon, Nov. 9th Persistent homology Edelsbrunner notes; lecture notes
Wed, Nov. 11th Stability of persistent homology and bottleneck distance Edelsbrunner notes; lecture notes
Mon, Nov. 16th Stability and curvature of cycles Edelsbrunner notes; lecture notes
Wed, Nov. 18th Curvature of cycles continued, smooth functions Edelsbrunner notes on curvature and smooth functions; lecture notes Homework 3 due Friday, November 20th (LaTeX source)
Mon, Nov. 23th Morse functions, Reeb graphs Edelsbrunner notes on Morse functions, transversality (just to state Morse inequalities), and Reeb graphs; lecture notes
Wed, Nov. 25th Reeb graphs on manifolds, closing thoughts Edelsbrunner notes; lecture notes Project reports due