One-Dimensional Computational Topology

CS 598 JGE, Fall 2017

Main  ❖  Schedule  ❖  Homework  ❖  Projects  ❖  References

There is no required textbook for this class; I will post electronic copies of relevant papers to this web site as the course progresses. Meanwhile, here is am incomplete list of background references, primarily surveys and textbooks. Key references are hilighted. I've deliberately omitted most references to branches of computational topology that this class won't touch.

Topology

• Allen Hatcher. Algebraic Topology. Cambridge University Press, 2001.
• Jiří Matoušek. Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. Springer, 2003.
• John Stillwell. Classical Topology and Combinatorial Group Theory. Springer, 1995.

Planar graphs and surface graphs

• Éric Colin de Verdiére. Algorithms for Embedded Graphs, May 2017.
• Jonathan L. Gross and Thomas W. Tucker. Topological Graph Theory. Dover Publications, 2001.
• Philip Klein and Shay Mozes. Optimization Algorithms for Planar Graphs, 2014. [Draft textbook, still in progress.]
• Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001.

Computational topology (more broadly)

• Nathan Dunfield, editor. The CompuTop.org Software Archive. Last updated April 8, 2016. [A collection of links to software for low-dimensional topology, especially 3-manifolds.]
• Herbert Edelsbrunner and John Harer. Computational Topology: An Introduction. AMS Press, 2010. [Emphasizes persistent homology and discrete Morse theory.]
• Robert Ghrist. Elementary Applied Topology, 2014.
• Tomasz Kaczynski, Konstantin Mischaikow, and Marian Mrozek. Computational Homology. Applied Mathematical Sciences 157, Springer, 2004. [What it says on the tin; emphasizes the homology of cube complexes. The algorithms are implemented as part of the CHomP project.]

Algorithms and data structures

• Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edition, 2008. [The standard reference for computational geometry.]
• Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. Algorithms. McGraw-Hill, 2006.
• Jeff Erickson. Algorithms, Etc., 2015. [Free lecture notes and other course materials.]
• Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2005.
• Pat Morin. Open Data Structures. Athabasca University Press, 2015. [Free textbook!]