Return to Revisions

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.
            Fig3 http://cs.smith.edu/%7Eorourke/MathOverflow/ShortestCycleFig3.jpg