Tightening non-simple paths and cycles on surfaces

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 ≥ 2, and no boundary, we construct in O(n² log n) time a tight octagonal decomposition of 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 complexity k in O(gnk) time, or the shortest cycle homotopic to a given cycle of complexity k in O(gnk log(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.

REFERENCES

• 1: Sergei Bespamyatnikh, Computing homotopic shortest paths in the plane, Journal of Algorithms, v.49 n.2, p.284-303, November 2003 [doi>10.1016/S0196-6774(03)00090-7]
• 2: S. Cabello, Y. Liu, A. Mantler, and J. Snoeyink. Testing homotopy for paths in the plane. Discrete Comput. Geom. 31:61--81, 2004.
• 3: S. Cabello and B. Mohar. Finding shortest non-separating and non-contractible cycles for topologically embedded graphs. Proc. 13th Annu. European Sympos. Algorithms, 2005. To appear.
• 4: É. Colin de Verdière. Raccourcissement de courbes et décomposition de surfaces {Shortening of Curves and Decomposition of Surfaces}. Ph.D. thesis, University of Paris 7, Dec. 2003. (http://www.di.ens.fr/~colin/textes/these.html).
• 5: É. Colin de Verdière and F. Lazarus. Optimal pants decompositions and shortest homotopic cycles on an orientable surface. Proc. 11th Sympos. Graph Drawing, 478--490, 2003. Lecture Notes Comput. Sci. 2912.
• 6: É. Colin de Verdière and F. Lazarus. Optimal system of loops on an orientable surface. Discrete Comput. Geom. 33(3):507--534, 2005.
• 7: M. Dehn. Transformation der Kurven auf zweiseitigen Flächen. Math. Ann. 72:413--421, 1912.
• 8: Tamal K. Dey , Sumanta Guha, Transforming curves on surfaces, Journal of Computer and System Sciences, v.58 n.2, p.297-325, April 1999 [doi>10.1006/jcss.1998.1619]
• 9: T. K. Dey and H. Schipper. A new technique to compute polygonal schema for 2-manifolds with application to null-homotopy detection. Discrete Comput. Geom. 14:93--110, 1995.
• 10: Alon Efrat , Stephen G. Kobourov , Anna Lubiw, Computing Homotopic Shortest Paths Efficiently, Proceedings of the 10th Annual European Symposium on Algorithms, p.411-423, September 17-21, 2002
• 11: David Eppstein, Dynamic generators of topologically embedded graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 12: D. B. A. Epstein. Curves on 2-manifolds and isotopies. Acta Mathematica 115:83--107, 1966.
• 13: J. Erickson and S. Har-Peled. Optimally cutting a surface into a disk. Discrete Comput. Geom. 31(1):37--59, 2004.
• 14: Jeff Erickson , Kim Whittlesey, Greedy optimal homotopy and homology generators, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 15: Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
• 16: A. Hatcher. Algebraic topology. Cambridge University Press, 2002. (http://www.math.cornell.edu/~hatcher/).
• 17: Monika R. Henzinger , Philip Klein , Satish Rao , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Journal of Computer and System Sciences, v.55 n.1, p.3-23, Aug. 1997 [doi>10.1006/jcss.1997.1493]
• 18: John Hershberger , Jack Snoeyink, Computing minimum length paths of a given homotopy class, Computational Geometry: Theory and Applications, v.4 n.2, p.63-97, June 1994 [doi>10.1016/0925-7721(94)90010-8]
• 19: Francis Lazarus , Michel Pocchiola , Gert Vegter , Anne Verroust, Computing a canonical polygonal schema of an orientable triangulated surface, Proceedings of the seventeenth annual symposium on Computational geometry, p.80-89, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378630]
• 20: J. H. Reif. Minimum s-t cut of a planar undirected network in O(n log2 (n)) time. SIAM J. Comput. 12(1):71--81, 1983.
• 21: Haijo Schipper, Determining contractibility of curves, Proceedings of the eighth annual symposium on Computational geometry, p.358-367, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142749]
• 22: J. Stillwell. Classical Topology and Combinatorial Group Theory. Springer-Verlag, New York, 1993.
• 23: Gert Vegter , Chee K. Yap, Computational complexity of combinatorial surfaces, Proceedings of the sixth annual symposium on Computational geometry, p.102-111, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98546]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory