Article

Splitting (complicated) surfaces is hard

Authors:

Erin W. Chambers,

Éric Colin de Verdière,

Francis Lazarus,

Kim WhittleseyAuthors Info & Claims

SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry

Pages 421 - 429

https://doi.org/10.1145/1137856.1137918

Published: 05 June 2006 Publication History

Abstract

Let M be an orientable combinatorial surface without boundary. A cycle on M is splitting if it has no self-intersections and it partitions M into two components, neither of which is homeomorphic to a disk. In other words, splitting cycles are simple, separating, and non-contractible. We prove that finding the shortest splitting cycle on a combinatorial surface is NP-hard but fixed-parameter tractable with respect to the surface genus. Specifically, we describe an algorithm to compute the shortest splitting cycle in g^O(g)n log n time.

References

[1]

E. M. Arkin, S. Khuller, and J. S. B. Mitchell. Geometric knapsack problems. Algorithmica 10:399--427, 1993.]]

Digital Library

[2]

J. Blömer. Computing sums of radicals in polynomial time. Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci., 670--677, 1991.]]

Digital Library

[3]

S. Cabello. Many distances in planar graphs. Proc. 17th Annu. ACM-SIAM Sympos. Discrete Algorithms, 1213--1220, 2006.]]

Digital Library

[4]

S. Cabello and B. Mohar. Finding shortest non-separating and non-contractible cycles for topologically embedded graphs. Proc. 13th Annu. European Sympos. Algorithms, 131--142, 2005. Lecture Notes in Computer Science 3669, Springer-Verlag.]]

Digital Library

[5]

J. Chen and Y. Han. Shortest paths on a polyhedron, part I: Computing shortest paths. Int. J. Comput. Geom. Appl. 6(2):127--144, 1996.]]

[6]

è. Colin de Verdière and J. Erickson. Tightening non-simple paths and cycles on surfaces. Proc. 17th Annu. ACM-SIAM Sympos. Discrete Algorithms, 192--201, 2006.]]

Digital Library

[7]

è. 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, Springer-Verlag.]]

[8]

è. Colin de Verdière and F. Lazarus. Optimal systems of loops on an orientable surface. Discrete Comput. Geom. 33(3):507--534, 2005.]]

Digital Library

[9]

P. Eades and D. Rappaport. The complexity of computing minimum separating polygons. Pattern Recogn. Lett. 14(9):715--718, 1993.]]

Digital Library

[10]

D. Eppstein. Finding the k shortest paths. SIAM J. Computing 28(2):652--673, 1998.]]

Digital Library

[11]

D. B. A. Epstein. Curves on 2-manifolds and isotopies. Acta Mathematica 115:83--107, 1966.]]

[12]

J. Erickson and S. Har-Peled. Optimally cutting a surface into a disk. Discrete Comput. Geom. 31(1):37--59, 2004.]]

Digital Library

[13]

J. Erickson and K. Whittlesey. Greedy optimal homotopy and homology generators. Proc. 16th Annu. ACM-SIAM Sympos. Discrete Algorithms, 1038--1046, 2005.]]

Digital Library

[14]

G. N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16(6):1004--1022, 1987.]]

Digital Library

[15]

J. Hass and P. Scott. Intersections of curves on surfaces. Israel J. Math. 51:90--120, 1985.]]

[16]

A. Hatcher. Algebraic Topology. Cambridge University Press, 2002. (http://www.math.cornell.edu/~hatcher/).]]

[17]

D. S. Johnson and C. H. Papadimitriou. Computational complexity and the traveling salesman problem. The Traveling Salesman Problem, 68--74, 1985. John Wiley & Sons.]]

[18]

M. Kutz. Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time. These proceedings, 2006.]]

Digital Library

[19]

F. Lazarus, M. Pocchiola, G. Vegter, and A. Verroust. Computing a canonical polygonal schema of an orientable triangulated surface. Proc. 17th Annu. ACM Sympos. Comput. Geom., 80--89, 2001.]]

Digital Library

[20]

J. S. B. Mitchell, D. M. Mount, and C. H. Papadimitriou. The discrete geodesic problem. SIAM J. Comput. 16(4):647--668, 1987.]]

Digital Library

[21]

B. Mohar and C. Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001.]]

[22]

J. Stillwell. Classical Topology and Combinatorial Group Theory. Springer-Verlag, New York, 1993.]]

[23]

J. Takahashi, H. Suzuki, and T. Nishizeki. Shortest noncrossing paths in plane graphs. Algorithmica 16:339--357, 1996.]]

[24]

A. Zomorodian. Topology for Computing. Cambridge University Press, 2005.]]

Digital Library

Cited By

Despré VLazarus F(2016)Some Triangulated Surfaces without Balanced SplittingGraphs and Combinatorics10.1007/s00373-016-1735-632:6(2339-2353)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1007/s00373-016-1735-6
Cabello SDevos MErickson JMohar B(2010)Finding one tight cycleACM Transactions on Algorithms10.1145/1824777.18247816:4(1-13)Online publication date: 3-Sep-2010
https://dl.acm.org/doi/10.1145/1824777.1824781
Chambers EErickson JNayyeri AHershberger JFogel E(2009)Minimum cuts and shortest homologous cyclesProceedings of the twenty-fifth annual symposium on Computational geometry10.1145/1542362.1542426(377-385)Online publication date: 8-Jun-2009
https://dl.acm.org/doi/10.1145/1542362.1542426
Show More Cited By

Index Terms

Splitting (complicated) surfaces is hard

Recommendations

Splitting (complicated) surfaces is hard

Let M be an orientable combinatorial surface. A cycle on M is splitting if it has no self-intersections and it partitions M into two components, neither of which is homeomorphic to a disk. In other words, splitting cycles are simple, separating, and non-...
Tightening Nonsimple Paths and Cycles on Surfaces

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 ...
Optimal pants decompositions and shortest homotopic cycles on an orientable surface

We consider the problem of finding a shortest cycle (freely) homotopic to a given simple cycle on a compact, orientable surface. For this purpose, we use a pants decomposition of the surface: a set of disjoint simple cycles that cut the surface into ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

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
University of California at Davis
,
Otfried Cheong
Korea Advanced Institute of Science and Technology

Copyright © 2006 ACM.

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.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG06

Sponsor:

SoCG06: 22nd Annual Symposium on Computational Geometry

June 5 - 7, 2006

Arizona, Sedona, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
193
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Despré VLazarus F(2016)Some Triangulated Surfaces without Balanced SplittingGraphs and Combinatorics10.1007/s00373-016-1735-632:6(2339-2353)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1007/s00373-016-1735-6
Cabello SDevos MErickson JMohar B(2010)Finding one tight cycleACM Transactions on Algorithms10.1145/1824777.18247816:4(1-13)Online publication date: 3-Sep-2010
https://dl.acm.org/doi/10.1145/1824777.1824781
Chambers EErickson JNayyeri AHershberger JFogel E(2009)Minimum cuts and shortest homologous cyclesProceedings of the twenty-fifth annual symposium on Computational geometry10.1145/1542362.1542426(377-385)Online publication date: 8-Jun-2009
https://dl.acm.org/doi/10.1145/1542362.1542426
Cabello SDeVos MErickson JMohar BTeng S(2008)Finding one tight cycleProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347140(527-531)Online publication date: 20-Jan-2008
https://dl.acm.org/doi/10.5555/1347082.1347140
Chambers EErickson JWorah PTeillaud M(2008)Testing contractibility in planar rips complexesProceedings of the twenty-fourth annual symposium on Computational geometry10.1145/1377676.1377721(251-259)Online publication date: 9-Jun-2008
https://dl.acm.org/doi/10.1145/1377676.1377721
Cabello SChambers EGabow H(2007)Multiple source shortest paths in a genus g graphProceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1283383.1283394(89-97)Online publication date: 7-Jan-2007
https://dl.acm.org/doi/10.5555/1283383.1283394
Segonne FPacheco JFischl B(2007)Geometrically Accurate Topology-Correction of Cortical Surfaces Using Nonseparating LoopsIEEE Transactions on Medical Imaging10.1109/TMI.2006.88736426:4(518-529)Online publication date: Apr-2007
https://doi.org/10.1109/TMI.2006.887364
Kutz MAmenta NCheong O(2006)Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear timeProceedings of the twenty-second annual symposium on Computational geometry10.1145/1137856.1137919(430-438)Online publication date: 5-Jun-2006
https://dl.acm.org/doi/10.1145/1137856.1137919

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents