skip to main content
10.1145/1137856.1137919acmconferencesArticle/Chapter ViewAbstractPublication PagessocgConference Proceedingsconference-collections
Article

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

Published: 05 June 2006 Publication History

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(n3/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 Chambers, èric Colin de Verdière, Jeff Erickson, Francis Lazarus, and Kim Whittlesey. Splitting (complicated) surfaces is hard. In Proc. 22nd ACM Symp. Computational Geometry, 2006.
[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 and Jeff Erickson. Tightening non-simple paths and cycles on surfaces. In Proc. 17th ACM-SIAM Sympos. Discrete Algorithms, pages 192--201, 2006.
[6]
èric Colin de Verdière and Francis Lazarus. Optimal system of loops on an orientable surface. In 43rd Symp. Foundations Computer Science, pages 627--636, 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. In Proc. 14th ACM-SIAM Sympos. Discrete Algorithms, pages 599--608, 2003.
[9]
Jeff Erickson and Sariel Har-Peled. Optimally cutting a surface into a disk. In Proc. 18th ACM Symp. Computational Geometry, pages 244--253, 2002.
[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 and Kim Whittlesey. Greedy optimal homotopy and homology generators. In Proc. 16th ACM-SIAM Sympos. Discrete Algorithms, pages 1038--1046, 2005.
[12]
Greg N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Computing, 16(6):1004--1022, 1987.
[13]
Allen Hatcher. Algebraic Topology. Cambridge University Press, 2002. available online from http://www.math.crnell.edu/~hatcher/.
[14]
Monika R. Henzinger, Philip N. Klein, Satish Rao, and Sairam Subramanian. Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci., 55(1):3--23, 1997.
[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.

Cited By

View all
  • (2024)Towards Geodesic Ridge Curve for Region-wise Linear Representation of Geodesic Distance FieldComputer Aided Geometric Design10.1016/j.cagd.2024.102291(102291)Online publication date: Apr-2024
  • (2023)A Variational Loop Shrinking Analogy for Handle and Tunnel Detection and Reeb Graph Construction on SurfacesComputer Graphics Forum10.1111/cgf.1476342:2(309-320)Online publication date: 23-May-2023
  • (2020)Topologically Trivial Closed Walks in Directed Surface GraphsDiscrete & Computational Geometry10.1007/s00454-020-00255-3Online publication date: 30-Nov-2020
  • Show More Cited By

Index Terms

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

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry
    June 2006
    500 pages
    ISBN:1595933409
    DOI:10.1145/1137856
    • Program Chairs:
    • Nina Amenta,
    • Otfried Cheong
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 05 June 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. computational topology
    2. efficient algorithm
    3. non-trivial cycles
    4. planar graph
    5. system of loops
    6. universal cover

    Qualifiers

    • Article

    Conference

    SoCG06

    Acceptance Rates

    Overall Acceptance Rate 625 of 1,685 submissions, 37%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)2
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 19 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Towards Geodesic Ridge Curve for Region-wise Linear Representation of Geodesic Distance FieldComputer Aided Geometric Design10.1016/j.cagd.2024.102291(102291)Online publication date: Apr-2024
    • (2023)A Variational Loop Shrinking Analogy for Handle and Tunnel Detection and Reeb Graph Construction on SurfacesComputer Graphics Forum10.1111/cgf.1476342:2(309-320)Online publication date: 23-May-2023
    • (2020)Topologically Trivial Closed Walks in Directed Surface GraphsDiscrete & Computational Geometry10.1007/s00454-020-00255-3Online publication date: 30-Nov-2020
    • (2017)Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of TerminalsAlgorithmica10.1007/s00453-016-0258-078:4(1206-1224)Online publication date: 1-Aug-2017
    • (2016)Global Minimum Cuts in Surface-Embedded GraphsEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_683(852-856)Online publication date: 22-Apr-2016
    • (2015)Discrete Systolic Inequalities and Decompositions of Triangulated SurfacesDiscrete & Computational Geometry10.1007/s00454-015-9679-953:3(587-620)Online publication date: 1-Apr-2015
    • (2014)Discrete Systolic Inequalities and Decompositions of Triangulated SurfacesProceedings of the thirtieth annual symposium on Computational geometry10.1145/2582112.2582127(335-344)Online publication date: 8-Jun-2014
    • (2014)Counting and Sampling Minimum Cuts in Genus $$g$$g GraphsDiscrete & Computational Geometry10.1007/s00454-014-9623-452:3(450-475)Online publication date: 1-Oct-2014
    • (2014)Global Minimum Cuts in Surface-Embedded GraphsEncyclopedia of Algorithms10.1007/978-3-642-27848-8_683-1(1-5)Online publication date: 4-Oct-2014
    • (2013)Shortest non-trivial cycles in directed and undirected surface graphsProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627843(352-364)Online publication date: 6-Jan-2013
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media