# 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. – 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 – theHigherGeometer Oct 27 '11 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 – Ryan Budney Oct 28 '11 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. – Ryan Budney Nov 24 '11 at 22:33

## 2 Answers

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. • 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. – theHigherGeometer 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.