# Computational Topology Paper

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. Oct 27, 2011 at 22:34
• One which everyone uses as an example Oct 27, 2011 at 23:15
• I don't know about tagging this computational-geometry, so I"m adding a computational-topology tag Oct 27, 2011 at 23:44
• The Stanford group has a preprints page. Go there, there's many good examples. For example: A. Zomorodian and G. Carlsson, “Localized homology” , Shape Modeling International , Lyon, France . Jan 2007 link Oct 28, 2011 at 14:33
• Your question is rather confusing. The answer you accepted gives an example paper which is very much not of the sort you requested. Nov 24, 2011 at 22:33

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.