Annotated bibliography on computational topology

Books

Topology. 2nd ed. James Munkres. Prentice Hall. 1999. [ Amazon.com ]

Algebraic Topology. Allen Hatcher. Cambridge University Press. 2002. [ | Amazon.com ]

Classical Topology and Combinatorial Group Theory. John Stillwell. Springer, 2005. [ Amazon.com ]

Geometry and Topology for Mesh Generation. Herbert Edelsbrunner. Cambridge University Press. 2001. [ Amazon.com ]

Topology for Computing. Afra Zomorodian. Cambridge University Press. 2004. [ WWW | Amazon.com ]

Homotopy

Transforming Curves on Surfaces. Tamal K. Dey and Sumanta Guha. (1999) J. Computer and System Sciences, Volume 58, Issue 2, pp. 297--325. (Special issue on the 36th FOCS)

Gives an optimal linear-time algorithm to decide if one closed curve on a triangulated 2-manifold can be continuously transformed to another, i.e., if the two curves are homotopic.

Testing Homotopy for Paths in the Plane. Sergio Cabello, Yuanxin Liu, Andrea Mantler, and Jack Snoeyink. (2002) Proc. 18th Symp. Computational Geometry (SoCG), pp. 160--169. [ ]

Computing Homotopic Shortest Paths Efficiently. Alon Efrat, Stephen G. Kobourov, and Anna Lubiw. (2002) Proc. European Symposium on Algorithms (ESA), pp. 411--423, LNCS 2461, Springer.

Greedy Optimal Homotopy and Homology Generators. Jeff Erickson and Kim Whittlesey. (2005) Proc. Symp. Discrete Algorithms (SODA), pp. 1038--1046, 2005. [ WWW ]

Homology

Computing Persistent Homology. Afra Zomorodian and Gunnar Carlsson. (2004) Proc. 20th Symp. Computational Geometry (SoCG), pp. 347--356. [ ]

Computing and Comprehending Topology: Persistence and Hierarchical Morse Complexes. Afra Zomorodian. (2001) Ph.D. Thesis, University of Illinois at Urbana-Champaign, Technical Report UIUCDCS-R-2001-2240. [ ]

Morse theory

Computing Morse Functions on Triangulated Manifolds. Ulrike Axen. (1999) In Proc. 10th Symp. Discrete Algorithms (SODA), pp. 850--851.

Morse Theory for Cell Complexes. Robin Forman. (1998) Advances in Math., vol. 184, no. 1, pp. 90--145. MR1612391 (99b:57050)

This paper presents a Morse theory for cell complexes, in particular for simplicial complexes, following the pattern of the classical Morse theory for smooth manifolds. Discrete Morse functions are defined, and analogues of the main theorems in Morse theory are given. This includes a sphere theorem in the following sense: If there is a Morse function with exactly 2 critical points on a manifold without boundary then the manifold is a sphere. Discrete gradient vector fields and the associated flows are also introduced, and the existence of self-indexing Morse functions is proved.

Discrete Morse Theory and the Cohomology Ring. Robin Forman. Trans. Amer. Math. Soc. 354 (2002), pp. 5063--5085.

Other articles on Morse theory by Robin Forman:

A User's Guide to Discrete Morse Theory.
Morse Theory and Evasiveness.

Optimal Discrete Morse Functions for 2-Manifolds. Thomas Lewiner, Hélio Lopes, and Geovan Tavares. (2003) Computational Geometry: Theory and Applications (CGTA), vol. 26, issue 3 (November 2003), pp. 221--233.

Once a Morse function has been defined on a manifold, then information about its topology can be deduced from its critical elements. The main objective of this paper is to introduce a linear algorithm to define optimal discrete Morse functions on discrete 2-manifolds, where optimality entails having the least number of critical elements. The algorithm presented is also extended to general finite cell complexes of dimension at most 2, with no guarantee of optimality.

Curves and optimal arrangements on surfaces

Optimally cutting a surface into a disk. Jeff Erickson and Sariel Har-Peled. (2004) Discrete and Computational Geometry, 31(1):37--59. (Special issue of invited papers from the 18th Annual ACM Symposium on Computational Geometry) Proc. 18th Symp. Computational Geometry (SoCG), pp. 244--253, 2002. [ WWW ]

Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs. Sergio Cabello and Bojan Mohar. (2005) [ PDF ]

Gives a faster algorithm than that of Erickson and Har-Peled for small genus. Uses an efficient data structure for finding shortest paths between k pairs of source and destination vertices in a planar graph.

Computing Shortest Non-Trivial Cycles on Orientable Surfaces of Bounded Genus in Almost Linear Time. Martin Kutz. Proc. SoCG, pp. 430--437, 2006 (Sedona, AZ). [ PDF ]

Splitting (Complicated) Surfaces is Hard. Erin Chambers, Eric Colin de Verdiere, Jeff Erickson, Francis Lazarus, and Kim Whittlesey. To appear at SoCG 2006. [ WWW ]

"A cycle on S is splitting if it has no self-intersections and it partitions S into two components, neither homeomorphic to a disk. In other words, splitting cycles are simple, separating, and non-contractible. We prove that finding the shortest splitting cycle on a combinatorial surface is NP-hard but fixed-parameter tractable with respect to the surface genus."

Pants Decomposition of the Punctured Plane. Sheung-Hung Poon and Shripad Thite. To appear at the 22nd European Workshop on Computational Geometry. [ ]

Surface reconstruction with topological guarantees

Sampling and Meshing a Surface with Guaranteed Topology and Geometry. S.-W. Cheng, T. K. Dey, and E. A. Ramos. (2004) Proc. 20th Symp. Computational Geometry (SoCG), pp. 280--289. [ ]

Isotopic Implicit Surface Meshing. Jean-Daniel Boissonnat, David Cohen-Steiner, and Gert Vegter. (2004) Proc. Symp. Theory of Computing (STOC), pp. 301--309. [ ]