SIAM Journal on Computing 39(8):3784–3813, 2010.

Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 192-201, 2006.

- Download journal version (final except for copy-editing):
- Download SODA version (© 2005 SIAM):
- Official SODA version from the ACM Digital Library (subscription or $5 fee required)

Abstract:

We describe algorithms to compute the shortest path homotopic to a given path, or the shortest cycle freely homotopic to a given cycle, on an orientable combinatorial surface. Unlike earlier results, our algorithms do not require the input path or cycle to be simple. Given a surface with complexity n, genus g>1, and no boundary, we construct in O(n^{2}logn) time atight octagonal decompositionof the surface—a set of simple cycles, each as short as possible in its free homotopy class, that decompose the surface into a complex of octagons meeting four at a vertex. After the surface is preprocessed, we can compute the shortest path homotopic to a given path of complexitykin O(gnk) time, or the shortest cycle homotopic to a given cycle of complexitykin O(gnklog (nk)) time. A similar algorithm computes shortest homotopic curves on surfaces with boundary or with genus 1. We also prove that the recent algorithms of Colin de Verdière and Lazarus for shortening embedded graphs and sets of cycles have running times polynomial in the complexity of the surface and the input curves, regardless of the surface geometry.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 26 Jan 2005