{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,29]],"date-time":"2023-05-29T20:10:13Z","timestamp":1685391013602},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,1,28]],"date-time":"2010-01-28T00:00:00Z","timestamp":1264636800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2010,12]]},"DOI":"10.1007\/s00454-010-9241-8","type":"journal-article","created":{"date-parts":[[2010,1,27]],"date-time":"2010-01-27T16:43:44Z","timestamp":1264610624000},"page":"912-930","source":"Crossref","is-referenced-by-count":12,"title":["Computing the Shortest Essential Cycle"],"prefix":"10.1007","volume":"44","author":[{"given":"Jeff","family":"Erickson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pratik","family":"Worah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,1,28]]},"reference":[{"key":"9241_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-18245-7","volume-title":"A Panoramic View of Riemannian Geometry","author":"M. Berger","year":"2003","unstructured":"Berger, M.: A Panoramic View of Riemannian Geometry. Springer, Berlin (2003)"},{"key":"9241_CR2","doi-asserted-by":"crossref","unstructured":"Borradaile, G., Lee, J.R., Sidiropoulos, A.: Randomly removing g handles at once. In: Proc. 25th Ann. Symp. Comput. Geom., pp. 371\u2013376 (2009)","DOI":"10.1145\/1542362.1542425"},{"key":"9241_CR3","volume-title":"Distance in Graphs","author":"F. Buckley","year":"1990","unstructured":"Buckley, F., Harary, F.: Distance in Graphs. Addison-Wesley, New York (1990)"},{"key":"9241_CR4","doi-asserted-by":"crossref","unstructured":"Cabello, S.: Many distances in planar graphs. In: Proc. 17th Ann. ACM-SIAM Symp. Discrete Algorithms, pp. 1213\u20131220 (2006)","DOI":"10.1145\/1109557.1109691"},{"key":"9241_CR5","unstructured":"Cabello, S., Chambers, E.W.: Multiple source shortest paths in a genus g graph. In: Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, pp. 89\u201397 (2007)"},{"key":"9241_CR6","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/s00454-006-1292-5","volume":"37","author":"S. Cabello","year":"2007","unstructured":"Cabello, S., Mohar, B.: Finding shortest non-separating and non-contractible cycles for topologically embedded graphs. Discrete Comput. Geom. 37, 213\u2013235 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"9241_CR7","unstructured":"Cabello, S., DeVos, M., Erickson, J., Mohar, B.: Finding one tight cycle. In: Proc. 19th Ann. ACM-SIAM Symp. Discrete Algorithms, pp. 527\u2013531 (2008)"},{"issue":"1\u20132","key":"9241_CR8","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.comgeo.2007.10.010","volume":"41","author":"E.W. Chambers","year":"2008","unstructured":"Chambers, E.W., Colin\u00a0de\u00a0Verdi\u00e8re, \u00c9., Erickson, J., Lazarus, F., Whittlesey, K.: Splitting (complicated) surfaces is hard. Comput. Geom. Theory Appl. 41(1\u20132), 94\u2013110 (2008)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9241_CR9","doi-asserted-by":"crossref","unstructured":"Chambers, E.W., Erickson, J., Nayyeri, A.: Minimum cuts and shortest homologous cycles. In: Proc. 25th Ann. ACM Symp. Comput. Geom., pp. 377\u2013385 (2009)","DOI":"10.1145\/1542362.1542426"},{"key":"9241_CR10","unstructured":"Colin de Verdi\u00e8re, \u00c9.: Shortening of curves and decomposition of surfaces. Ph.D. thesis, Universit\u00e9 Paris 7, December 2003 ( http:\/\/www.di.ens.fr\/users\/colin\/textes\/these.html.en )"},{"key":"9241_CR11","unstructured":"Colin de Verdi\u00e8re, \u00c9.: Personal communication (2004)"},{"key":"9241_CR12","doi-asserted-by":"crossref","unstructured":"Colin de Verdi\u00e8re, \u00c9., Erickson, J.: Tightening non-simple paths and cycles on surfaces. In: Proc. 17th Ann. ACM-SIAM Symp. Discrete Algorithms, pp. 192\u2013201 (2006)","DOI":"10.1145\/1109557.1109580"},{"key":"9241_CR13","doi-asserted-by":"crossref","unstructured":"Colin de Verdi\u00e8re, \u00c9., Lazarus, F.: Optimal pants decompositions and shortest homotopic cycles on an orientable surface. J. ACM 54(4) (2007)","DOI":"10.1145\/1255443.1255446"},{"key":"9241_CR14","unstructured":"Demaine, E.D., Hajiaghayi, M., Mohar, B.: Approximation algorithms via contraction decomposition. In: Proc. 18th Ann. ACM-SIAM Symp. Discrete Algorithms, pp. 278\u2013287 (2007)"},{"key":"9241_CR15","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269\u2013271 (1959)","journal-title":"Numer. Math."},{"key":"9241_CR16","unstructured":"Eppstein, D.: Dynamic generators of topologically embedded graphs. In: Proc. 15th Ann. ACM-SIAM Symp. Discrete Algorithms, pp. 599\u2013608 (2004)"},{"key":"9241_CR17","unstructured":"Eppstein, D.: Squarepants in a tree: Sum of subtree clustering and hyperbolic pants decomposition. In: Proc. 18th ACM-SIAM Symp. Discrete Algorithms, pp. 29\u201338 (2007)"},{"issue":"1","key":"9241_CR18","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s00454-003-2948-z","volume":"31","author":"J. Erickson","year":"2004","unstructured":"Erickson, J., Har-Peled, S.: Optimally cutting a surface into a disk. Discrete Comput. Geom. 31(1), 37\u201359 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"9241_CR19","unstructured":"Erickson, J., Whittlesey, K.: Greedy optimal homotopy and homology generators. In: Proc. 16th Ann. ACM-SIAM Symp. Discrete Algorithms, pp. 1038\u20131046 (2005)"},{"key":"9241_CR20","unstructured":"Farb, B., Margalit, D.: A primer on mapping class groups. Preprint, Version 3.1, June 1 (2009) ( http:\/\/www.math.utah.edu\/~margalit\/primer\/ )"},{"key":"9241_CR21","unstructured":"Guskov, I., Wood, Z.: Topological noise removal. In: Proc. Graph. Interface, pp. 19\u201326 (2001)"},{"issue":"2","key":"9241_CR22","doi-asserted-by":"crossref","first-page":"185","DOI":"10.4310\/jdg\/1214436096","volume":"16","author":"F. Harary","year":"1981","unstructured":"Harary, F., Nieminen, J.: Convexity in graphs. J. Differ. Geom. 16(2), 185\u2013190 (1981)","journal-title":"J. Differ. Geom."},{"key":"9241_CR23","series-title":"Annals of Math. Studies","volume-title":"Combinatorics of Train Tracks","author":"J.L. Harer","year":"1992","unstructured":"Harer, J.L., Penner, R.C.: Combinatorics of Train Tracks. Annals of Math. Studies, vol.\u00a0125. Princeton University Press, Princeton (1992)"},{"key":"9241_CR24","volume-title":"Algebraic Topology","author":"A. Hatcher","year":"2001","unstructured":"Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2001)"},{"issue":"1","key":"9241_CR25","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"M.R. Henzinger","year":"1997","unstructured":"Henzinger, M.R., Klein, P., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55(1), 3\u201323 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"9241_CR26","doi-asserted-by":"crossref","unstructured":"Indyk, P., Sidiropoulos, A.: Probabilistic embeddings of bounded genus graphs into planar graphs. In: Proc. 23rd Ann. ACM Symp. Comput. Geom., pp. 204\u2013209 (2007)","DOI":"10.1145\/1247069.1247107"},{"key":"9241_CR27","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Mohar, B.: Graph and map isomorphism and all polyhedral embeddings in linear time. In: Proc. 40th Ann. ACM Symp. Theory Comput., pp. 471\u2013480 (2008)","DOI":"10.1145\/1374376.1374443"},{"key":"9241_CR28","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Reed, B.: Computing crossing number in linear time. In: Proc. 39th Ann. ACM Symp. Theory Comput., pp. 382\u2013390 (2007)","DOI":"10.1145\/1250790.1250848"},{"key":"9241_CR29","doi-asserted-by":"crossref","unstructured":"Kutz, M.: Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time. In: Proc. 22nd Ann. ACM Symp. Comput. Geom., pp. 430\u2013438 (2006)","DOI":"10.1145\/1137856.1137919"},{"key":"9241_CR30","doi-asserted-by":"crossref","unstructured":"Lazarus, F., Pocchiola, M., Vegter, G., Verroust, A.: Computing a canonical polygonal schema of an orientable triangulated surface. In: Proc. 17th Ann. ACM Symp. Comput. Geom., pp. 80\u201389 (2001)","DOI":"10.1145\/378583.378630"},{"key":"9241_CR31","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"B. Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins Press, Baltimore (2001)"},{"key":"9241_CR32","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U., Vazirani, V.: Matching is as easy as matrix inversion. Combinatorica 7, 105\u2013113 (1987)","journal-title":"Combinatorica"},{"key":"9241_CR33","unstructured":"Poon, S.-H., Thite, S.: Pants decomposition of the punctured plane. In: Proc. 22nd European Workshop Comput. Geom., pp. 99\u2013102 (2006). arXiv:cs.CG\/0602080"},{"key":"9241_CR34","series-title":"North-Holland Mathematics Studies","volume-title":"Geometry of Riemann Surfaces and Teichm\u00fcller Spaces","author":"M. Sepp\u00e4l\u00e4","year":"1992","unstructured":"Sepp\u00e4l\u00e4, M., Sorvali, T.: Geometry of Riemann Surfaces and Teichm\u00fcller Spaces. North-Holland Mathematics Studies, vol.\u00a0169. North-Holland, Amsterdam (1992)"},{"issue":"2","key":"9241_CR35","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0095-8956(90)90115-G","volume":"48","author":"C. Thomassen","year":"1990","unstructured":"Thomassen, C.: Embeddings of graphs with no short noncontractible cycles. J. Comb. Theory Ser. B 48(2), 155\u2013177 (1990)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9241_CR36","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546945","volume-title":"Topology and Computing","author":"A. Zomorodian","year":"2005","unstructured":"Zomorodian, A.: Topology and Computing. Cambridge University Press, Cambridge (2005)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-010-9241-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-010-9241-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-010-9241-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,29]],"date-time":"2023-05-29T19:54:42Z","timestamp":1685390082000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-010-9241-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1,28]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["9241"],"URL":"https:\/\/doi.org\/10.1007\/s00454-010-9241-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1,28]]}}}