Finding shortest contractible and shortest separating cycles in embedded graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Finding shortest contractible and shortest separating cycles in embedded graphs

Full text

Pdf (448 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms table of contents

New York, New York

Pages 616-624

Year of Publication: 2009

Author

Sergio Cabello

University of Ljubljana, Slovenia

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 55, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

We give a polynomial-time algorithm to find a shortest contractible cycle (i.e. a closed walk without repeated vertices) in a graph embedded in a surface. This answers a question posed by Hutchinson. In contrast, we show that finding a shortest contractible cycle through a given vertex is NP-hard. We also show that finding a shortest separating cycle in an embedded graph is NP-hard. This answers a question posed by Mohar and Thomassen.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Sergio Cabello, Many distances in planar graphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1213-1220, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109691]
	2	Sergio Cabello , Erin W. Chambers, Multiple source shortest paths in a genus g graph, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.89-97, January 07-09, 2007, New Orleans, Louisiana
	3	Sergio Cabello , Matt DeVos , Jeff Erickson , Bojan Mohar, Finding one tight cycle, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.527-531, January 20-22, 2008, San Francisco, California
	4	Sergio Cabello , Bojan Mohar, Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs, Discrete & Computational Geometry, v.37 n.2, p.213-235, February 2007 [doi>10.1007/s00454-006-1292-5]
	5	Erin W. Chambers , Éric Colin de Verdière , Jeff Erickson , Francis Lazarus , Kim Whittlesey, Splitting (complicated) surfaces is hard, Computational Geometry: Theory and Applications, v.41 n.1-2, p.94-110, October, 2008 [doi>10.1016/j.comgeo.2007.10.010]
	6	É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]
	7	É. Colin de Verdière and F. Lazarus. Optimal system of loops on an orientable surface. Discrete Comput. Geom., 33:507--534, 2005. Preliminary version in FOCS '02.
	8	Éric Colin De Verdière , Francis Lazarus, Optimal pants decompositions and shortest homotopic cycles on an orientable surface, Journal of the ACM (JACM), v.54 n.4, p.18-es, July 2007 [doi>10.1145/1255443.1255446]
	9	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
	10	J. Erickson and S. Har-Peled. Optimally cutting a surface into a disk. Discrete Comput. Geom., 31:37--59, 2004. Preliminary version in SOCG '02.
	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	H. N. Gabow , S. N. Maheshwari , L. J. Osterweil, On Two Problems in the Generation of Program Test Paths, IEEE Transactions on Software Engineering, v.2 n.3, p.227-231, May 1976 [doi>10.1109/TSE.1976.233819]
	13	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	14	A. Hatcher. Algebraic Topology. Cambridge University Press, 2001. Available at http://www.math.cornell.edu/~hatcher/.
	15	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]
	16	Viggo Kann, Polynomially bounded minimization problems that are hard to approximate, Nordic Journal of Computing, v.1 n.3, p.317-331, Fall 1994
	17	Martin Kutz, Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137919]
	18	W. S. Massey. Algebraic Topology: An Introduction. Springer Verlag, 1967.
	19	B. Mohar and C. Thomassen. Graphs on Surfaces. Johns Hopkins University Press, Baltimore, 2001.
	20	H. Ren and M. Deng. Short cycle structures for graphs on surfaces and an open problem of Mohar and Thomassen. Science in China Series A: Mathematics, 49(2):212--224, 2006.
	21	J. Stillwell. Classical Topology and Combinatorial Group Theory. Springer-Verlag, New York, 1993.
	22	C. Thomassen, Embeddings of graphs with no short noncontractible cycles, Journal of Combinatorial Theory Series B, v.48 n.2, p.155-177, Apr. 1990 [doi>10.1016/0095-8956(90)90115-G]
	23	C. Thomassen. Recent results on graph embeddings. In Y. Alavi, G. Chartrand, O. R. Ollerman, and A. J. Schwenk, editors, Graph Theory, Combinatorics, and Applications, pages 1093--1103. John Wiley and Sons, 1991.