Computational Topology Paper

Hi

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

-
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

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.