MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


I am delving into the field of Computational Topology. I am aware of the books in this field, but

could anybody tell me a nice relevant paper in this field which tackles a "typical" Computational Topology problem?

Thank you

share|cite|improve this question
What do you mean by "typical"? One which everyone is considering? One which everyone uses as an example? One which motivated the subject? One that your lecturer works on? etc. – Yemon Choi Oct 27 '11 at 22:34
One which everyone uses as an example – user695652 Oct 27 '11 at 23:15
I don't know about tagging this computational-geometry, so I"m adding a computational-topology tag – David Roberts Oct 27 '11 at 23:44
It really depends on the flavour of computational topology you're interested in. For example, computational 3-manifold topology -- things like the 3-sphere recognition algorithm -- have a very different flavour than say the Edelsbrunner / Harer text. – Ryan Budney Oct 27 '11 at 23:49
Oh thanks I wasn't aware of this. Yes I meant more the Edelsbrunner type. – user695652 Oct 27 '11 at 23:50
up vote 4 down vote accepted

Perhaps the paper by Jeff Erickson and Pratik Worah, "Computing the Shortest Essential Cycle," Discrete & Computational Geometry, Volume 44, Issue 4, December 2010 (PDF link), might serve your purposes. They compute the shortest "simple cycle that cannot be continuously deformed to a point or a single boundary." The input to their problem is "a combinatorial surface, which is an abstract topological surface $M$ together with an edge-weighted graph $G$ cellularly embedded on $M$." If $n$ is the complexity of the surface, their algorithm runs in $O(n^2 \log n)$ time, and faster, $O( n \log n)$, when the genus and number of boundaries are considered fixed. This paper is, in some sense, a culmination of a series of papers finding cycles on combinatorial surfaces, often to cut them along the cycles to produces simpler surfaces.

share|cite|improve this answer
This is nice. It harks back to the early days of Riemann surfaces, when 'connectedness' (=genus) was defined by curves along which one cut the surface. – David Roberts Oct 28 '11 at 0:56
Thanks you for the nice paper suggestion, that was what I was looking for. – user695652 Oct 28 '11 at 15:36

The interesting books i know of are Edelsbrunner/Harer and Zomordian's thesis. On similar topics, the Comtop group at Stanford has very detailed information.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.