Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time

ABSTRACT

We present an algorithm that computes a shortest non-contractible and a shortest non-separating cycle on an orientable combinatorial surface of bounded genus in O(n log n) time, where n denotes the complexity of the surface. This solves a central open problem in computational topology, improving upon the current-best O(n^3/2)-time algorithm by Cabello and Mohar (ESA 2005). Our algorithm is based on universal-cover constructions to find short cycles and makes extensive use of existing tools from the field.

REFERENCES

• 1: Glen E. Bredon. Topology and Geometry. Springer, 1993.
• 2: Sergio Cabello and Bojan Mohar. Finding shortest non-separating and non-contractible cycles for topologically embedded graphs. In Proceedings 13th European Symp. Algorithms, pages 131--142, 2005. Full version at http://www.fmf.uni-lj.si/~cabello/publications/.
• 3: Erin W. Chambers , Éric Colin de Verdière , Jeff Erickson , Francis Lazarus , Kim Whittlesey, Splitting (complicated) surfaces is hard, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137918]
• 4: èric Colin de Verdière. Shortening of Curves and Decomposition of Surfaces. PhD thesis, Université Paris 7, 2003. available from http://www.di.ens.fr/~colin/.
• 5: Éric Colin de Verdière , Jeff Erickson, Tightening non-simple paths and cycles on surfaces, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.192-201, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109580]
• 6: Éric Colin de Verdière , Francis Lazarus, Optimal System of Loops on an Orientable Surface, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.627-636, November 16-19, 2002
• 7: èric Colin de Verdière and Francis Lazarus. Optimal pants decompositions and shortest homotopic cycles on an orientable surface. In Proc. 11th Symp. Graph Drawing, pages 478--490, 2003.
• 8: 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
• 9: Jeff Erickson , Sariel Har-Peled, Optimally cutting a surface into a disk, Proceedings of the eighteenth annual symposium on Computational geometry, p.244-253, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513430]
• 10: Jeff Erickson and Sariel Har-Peled. Optimally cutting a surface into a disk. Discrete & Computational Geometry, 31(1):37--59, 2004.
• 11: 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
• 12: 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]
• 13: Allen Hatcher. Algebraic Topology. Cambridge University Press, 2002. available online from http://www.math.crnell.edu/~hatcher/.
• 14: 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 ]
• 15: Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. John Hopkins University Press, 2001.
• 16: John H. Reif. Minimum s-t cut of a planar undirected network in O(n log2(n)) time. SIAM J. Computing, 12(1):71--81, 1983.

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
computational topology, efficient algorithm, non-trivial cycles, planar graph, system of loops, universal cover