CS 598: Computational Topology (Fall 2009)

About  ❖  Schedule  ❖  References  ❖  Coursework  ❖  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 a list of background references, primarily textbooks and recent surveys. Key references for the course are highlighted. Many of the other references focus on material that we will not cover at all in the course; I include them primarily to give some sense of the diversity of the field.

Computational topology

• Nathan Dunfield, editor. The CompuTop.org Software Archive. [A collection of links to software for low-dimensional topology, especially 3-manifolds.]
• Herbert Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge University Press, 2001. [Emphasizes mesh generation and simplification; includes a thorough survey of combinatorial topology.]
• Herbert Edelsbrunner and John Harer. Computational Topology: An Introduction. AMS Press, 2009.
• 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.]
• Sergei Matveev. Algorithmic Topology and Classification of 3-Manifolds. 2nd edition, Springer, 2007. [Emphasizes 3-manifold computation, building up to an algorithm for recognizing of Haken 3-manifolds via normal surface theory.]
• Sanjay Rama, edtior. Topological Data Structures for Surfaces: An Introduction to Geographical Information Science. Wiley, 2005. [Emphasizes data structures for geographic information systems.]
• Günter Rote and Gert Vegter. Computational topology: an introduction. Chapter 7 of Effective Computational Geometry for Curves and Surfaces (Jean-Daniel Boissonnat and Monique Teillaud, editors), pp. 277–312. Mathematics and Visualization, Springer-Verlag, 2006. [A survey of combinatorial (not really computational) topology, emphasizing simplicial homology and Morse theory.]
• Afra Zomorodian. Topology for Computing. Cambridge Monographs on Applied and Computational Mathematics 16. Cambridge University Press, 2005. [Emphasizes persistent homology and Morse theory.]

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 Milnor. Topology from the Differentiable Viewpoint. Princeton University Press, 1997.
• John Stillwell. Classical Topology and Combinatorial Group Theory. Springer, 1995.

Topological graph theory

• Lowell W. Beineke and Robin J. Wilson, editors. Topics in Topological Graph Theory. Encyclopedia of Mathematics and its Applications 128, Cambridge University Press, 2009.
• Peter Giblin. Graphs, Surfaces, and Homology, 3rd edition. Cambridge University Press, 2010.
• Jonathan L. Gross and Thomas W. Tucker. Topological Graph Theory. Dover Publications, 2001.
• Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001.

Algorithms

• 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.]
• Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press/McGraw-Hill, 2001.
• Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. Algorithms. McGraw-Hill, 2006.
• Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2005.
• Jeff's algorithms notes.