{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:29:04Z","timestamp":1750307344972,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":47,"publisher":"ACM","license":[{"start":{"date-parts":[[2011,6,13]],"date-time":"2011-06-13T00:00:00Z","timestamp":1307923200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2011,6,13]]},"DOI":"10.1145\/1998196.1998231","type":"proceedings-article","created":{"date-parts":[[2011,6,14]],"date-time":"2011-06-14T14:45:32Z","timestamp":1308062732000},"page":"236-243","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Shortest non-trivial cycles in directed surface graphs"],"prefix":"10.1145","author":[{"given":"Jeff","family":"Erickson","sequence":"first","affiliation":[{"name":"University of Illinois, Urbana-Champaign, Urbana, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Symp. Theoretical Aspects Comput. Sci., 171--182","author":"Borradaile G.","year":"2009","unstructured":"G. Borradaile , E. D. Demaine , and S. Tazari . Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Proc. 26th Int . Symp. Theoretical Aspects Comput. Sci., 171--182 , 2009 . Leibniz Int. Proc. Informatics 3, Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik . http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2009\/1835. G. Borradaile, E. D. Demaine, and S. Tazari. Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Proc. 26th Int. Symp. Theoretical Aspects Comput. Sci., 171--182, 2009. Leibniz Int. Proc. Informatics 3, Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2009\/1835."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502798"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542362.1542425"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109691"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721840"},{"key":"e_1_3_2_1_6_1","volume-title":"Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 89--97","author":"Cabello S.","year":"2007","unstructured":"S. Cabello and E. W. Chambers . Multiple source shortest paths in a genus g graph . Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 89--97 , 2007 . S. Cabello and E. W. Chambers. Multiple source shortest paths in a genus g graph. Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 89--97, 2007."},{"key":"e_1_3_2_1_7_1","unstructured":"S. Cabello E. W. Chambers and J. Erickson. Multiple-source shortest paths in embedded graphs. Full version of cc-msspg-07 in preparation. S. Cabello E. W. Chambers and J. Erickson. Multiple-source shortest paths in embedded graphs. Full version of cc-msspg-07 in preparation."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810959.1810988"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810959.1810987"},{"key":"e_1_3_2_1_10_1","volume-title":"Preprint","author":"Cabello S.","year":"2010","unstructured":"S. Cabello , \u00c9. Colin de Verdi\u00e8re, and F. Lazarus. Finding cycles with topological properties in embedded graphs . Preprint , October 2010 . http:\/\/www.di.ens.fr\/ colin\/textes\/09truecycle.pdf. S. Cabello, \u00c9. Colin de Verdi\u00e8re, and F. Lazarus. Finding cycles with topological properties in embedded graphs. Preprint, October 2010. http:\/\/www.di.ens.fr\/ colin\/textes\/09truecycle.pdf."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824781"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1292-5"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.10.010"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536453"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542362.1542426"},{"volume-title":"Proc. 18th Ann. Europ. Symp. Algorithms, 100--111","year":"2010","key":"e_1_3_2_1_16_1","unstructured":"\u00c9. Colin de Verdi\u00e8re. Shortest cut graph of a surface with prescribed vertex set . Proc. 18th Ann. Europ. Symp. Algorithms, 100--111 , 2010 . Lecture Notes Comput. Sci. 6347. \u00c9. Colin de Verdi\u00e8re. Shortest cut graph of a surface with prescribed vertex set. Proc. 18th Ann. Europ. Symp. Algorithms, 100--111, 2010. Lecture Notes Comput. Sci. 6347."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/090761653"},{"key":"e_1_3_2_1_18_1","volume-title":"Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 278--287","author":"Demaine E. D.","year":"2007","unstructured":"E. D. Demaine , M. Hajiaghayi , and B. Mohar . Approximation algorithms via contraction decomposition . Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 278--287 , 2007 . E. D. Demaine, M. Hajiaghayi, and B. Mohar. Approximation algorithms via contraction decomposition. Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, 278--287, 2007."},{"key":"e_1_3_2_1_19_1","volume-title":"Proc. 14th Ann. ACM-SIAM Symp. Discrete Algorithms, 599--608, 2003","author":"Eppstein D.","year":"2070","unstructured":"D. Eppstein . Dynamic generators of topologically embedded graphs . Proc. 14th Ann. ACM-SIAM Symp. Discrete Algorithms, 599--608, 2003 . ArXiv:\\hrefhttp:\/\/arxiv.org\/abs\/cs.DS\/0 2070 82cs.DS\/0207082. D. Eppstein. Dynamic generators of topologically embedded graphs. Proc. 14th Ann. ACM-SIAM Symp. Discrete Algorithms, 599--608, 2003. ArXiv:\\hrefhttp:\/\/arxiv.org\/abs\/cs.DS\/0207082cs.DS\/0207082."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873666"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2948-z"},{"key":"e_1_3_2_1_22_1","volume-title":"Proc. 22nd Ann. ACM-SIAM Symp. Discrete Algorithms, 1166--1176","author":"Erickson J.","year":"2011","unstructured":"J. Erickson and A. Nayyeri . Shortest homologous cycles and minimum cuts via homology covers . Proc. 22nd Ann. ACM-SIAM Symp. Discrete Algorithms, 1166--1176 , 2011 . J. Erickson and A. Nayyeri. Shortest homologous cycles and minimum cuts via homology covers. Proc. 22nd Ann. ACM-SIAM Symp. Discrete Algorithms, 1166--1176, 2011."},{"key":"e_1_3_2_1_23_1","volume-title":"Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 1038--1046","author":"Erickson J.","year":"2005","unstructured":"J. Erickson and K. Whittlesey . Greedy optimal homotopy and homology generators . Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 1038--1046 , 2005 . J. Erickson and K. Whittlesey. Greedy optimal homotopy and homology generators. Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 1038--1046, 2005."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9241-8"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_3_2_1_26_1","volume-title":"Topological graph theory","author":"Gross J. L.","year":"2001","unstructured":"J. L. Gross and T. W. Tucker . Topological graph theory . Dover Publications , 2001 . J. L. Gross and T. W. Tucker. Topological graph theory. Dover Publications, 2001."},{"key":"e_1_3_2_1_27_1","volume-title":"Proc. Graphics Interface, 19--26","author":"Guskov I.","year":"2001","unstructured":"I. Guskov and Z. Wood . Topological noise removal . Proc. Graphics Interface, 19--26 , 2001 . I. Guskov and Z. Wood. Topological noise removal. Proc. Graphics Interface, 19--26, 2001."},{"key":"e_1_3_2_1_28_1","volume-title":"Cambridge University Press","author":"Hatcher A.","year":"2001","unstructured":"A. Hatcher . Algebraic Topology . Cambridge University Press , 2001 . http:\/\/www.math.cornell.edu\/hatcher\/. A. Hatcher. Algebraic Topology. Cambridge University Press, 2001. http:\/\/www.math.cornell.edu\/hatcher\/."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247069.1247107"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208012"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993679"},{"key":"e_1_3_2_1_33_1","volume-title":"Preprint","author":"Italiano G. F.","year":"2010","unstructured":"G. F. Italiano and P. Sankowski . Improved minimum cuts and maximum flows in undirected planar graphs . Preprint , November 2010 . ArXiv:http:\/\/arxiv.org\/abs\/1011.28431011.2843. G. F. Italiano and P. Sankowski. Improved minimum cuts and maximum flows in undirected planar graphs. Preprint, November 2010. ArXiv:http:\/\/arxiv.org\/abs\/1011.28431011.2843."},{"issue":"1","key":"e_1_3_2_1_34_1","first-page":"37","article-title":"Minimum cut in directed planar networks","volume":"28","author":"Janiga L.","year":"1992","unstructured":"L. Janiga and V. Koubek . Minimum cut in directed planar networks . Kybernetika 28 ( 1 ): 37 -- 49 , 1992 . L. Janiga and V. Koubek. Minimum cut in directed planar networks. Kybernetika 28(1):37--49, 1992.","journal-title":"Kybernetika"},{"key":"e_1_3_2_1_35_1","volume-title":"Symp. Theoretical Aspects Comput. Sci., 117--128","author":"Kaplan H.","year":"2011","unstructured":"H. Kaplan and Y. Nussbaum . Minimum $s-t$ cut in undirected planar graphs when the source and the sink are close. Proc. 28th Int . Symp. Theoretical Aspects Comput. Sci., 117--128 , 2011 . Leibniz Int. Proc. Informatics 9, Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik . http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2011\/3004. H. Kaplan and Y. Nussbaum. Minimum $s-t$ cut in undirected planar graphs when the source and the sink are close. Proc. 28th Int. Symp. Theoretical Aspects Comput. Sci., 117--128, 2011. Leibniz Int. Proc. Informatics 9, Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2011\/3004."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374443"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250848"},{"key":"e_1_3_2_1_38_1","volume-title":"Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 146--155","author":"Klein P. N.","year":"2005","unstructured":"P. N. Klein . Multiple-source shortest paths in planar graphs . Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 146--155 , 2005 . P. N. Klein. Multiple-source shortest paths in planar graphs. Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, 146--155, 2005."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137919"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"Mohar B.","year":"2001","unstructured":"B. Mohar and C. Thomassen . Graphs on Surfaces . Johns Hopkins University Press , 2001 . B. Mohar and C. Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_3_2_1_42_1","first-page":"71","article-title":"cut of a planar undirected network in O(n log2 n) time. phSIAM J","volume":"12","author":"Reif J.","year":"1983","unstructured":"J. Reif . Minimum $s$-$t$ cut of a planar undirected network in O(n log2 n) time. phSIAM J . Comput. 12 : 71 -- 81 , 1983 . J. Reif. Minimum $s$-$t$ cut of a planar undirected network in O(n log2 n) time. phSIAM J. Comput. 12:71--81, 1983.","journal-title":"Comput."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4372-4","volume-title":"Classical Topology and Combinatorial Group Theory","author":"Stillwell J.","year":"1993","unstructured":"J. Stillwell . Classical Topology and Combinatorial Group Theory , 2 nd edition. Graduate Texts in Mathematics 72. Springer-Verlag , 1993 . J. Stillwell. Classical Topology and Combinatorial Group Theory, 2nd edition. Graduate Texts in Mathematics 72. Springer-Verlag, 1993.","edition":"2"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90115-G"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1538"},{"key":"e_1_3_2_1_46_1","volume-title":"Preprint","author":"Wolff-Nilsen C.","year":"2010","unstructured":"C. Wolff-Nilsen . Min st-cut of a planar graph in O(n log log n) time . Preprint , July 2010 . ArXiv : http:\/\/arxiv.org\/abs\/1007.36091007.3609. C. Wolff-Nilsen. Min st-cut of a planar graph in O(n log log n) time. Preprint, July 2010. ArXiv: http:\/\/arxiv.org\/abs\/1007.36091007.3609."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/990002.990007"}],"event":{"name":"SoCG '11: Symposium on Computational Geometry","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Paris France","acronym":"SoCG '11"},"container-title":["Proceedings of the twenty-seventh annual symposium on Computational geometry"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1998196.1998231","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1998196.1998231","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:06:27Z","timestamp":1750244787000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1998196.1998231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,13]]},"references-count":47,"alternative-id":["10.1145\/1998196.1998231","10.1145\/1998196"],"URL":"https:\/\/doi.org\/10.1145\/1998196.1998231","relation":{},"subject":[],"published":{"date-parts":[[2011,6,13]]},"assertion":[{"value":"2011-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}