{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T20:40:54Z","timestamp":1736023254175,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540291183"},{"type":"electronic","value":"9783540319511"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11561071_14","type":"book-chapter","created":{"date-parts":[[2005,10,6]],"date-time":"2005-10-06T12:46:24Z","timestamp":1128602784000},"page":"131-142","source":"Crossref","is-referenced-by-count":4,"title":["Finding Shortest Non-separating and Non-contractible Cycles for Topologically Embedded Graphs"],"prefix":"10.1007","author":[{"given":"Sergio","family":"Cabello","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bojan","family":"Mohar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/jgt.3190020102","volume":"2","author":"M.O. Albertson","year":"1978","unstructured":"Albertson, M.O., Hutchinson, J.P.: On the independence ratio of a graph. J. Graph Theory\u00a02, 1\u20138 (1978)","journal-title":"J. Graph Theory"},{"key":"14_CR2","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1006\/jcss.1998.1619","volume":"58","author":"T.K. Dey","year":"1999","unstructured":"Dey, T.K., Guha, S.: Transforming curves on surfaces. J. Comput. Syst. Sci.\u00a058, 297\u2013325 (1999); Preliminary version in FOCS 1995","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR3","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BF02570697","volume":"14","author":"T.K. Dey","year":"1995","unstructured":"Dey, T.K., Schipper, H.: A new technique to compute polygonal schema for 2-manifolds with application to null-homotopy detection. Discrete Comput. Geom.\u00a014, 93\u2013110 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"14_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/3-540-62559-3_14","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H. Djidjev","year":"1997","unstructured":"Djidjev, H.: On-line algorithms for shortest path problems on planar digraphs. In: D\u2019Amore, F., Marchetti-Spaccamela, A., Franciosa, P.G. (eds.) WG 1996. LNCS, vol.\u00a01197, pp. 151\u2013165. Springer, Heidelberg (1997)"},{"key":"14_CR5","unstructured":"de Verdi\u00e8re, \u00c9.C.: Shortening of curves and decomposition of surfaces. PhD thesis, University Paris 7 (December 2003)"},{"key":"#cr-split#-14_CR6.1","doi-asserted-by":"crossref","unstructured":"de Verdi??re, ??.C., Lazarus, F.: Optimal system of loops on an orientable surface. In: FOCS 2002, pp. 627???636 (2002);","DOI":"10.1109\/SFCS.2002.1181986"},{"key":"#cr-split#-14_CR6.2","unstructured":"To appear in Discrete Comput. Geom."},{"key":"14_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1007\/978-3-540-24595-7_45","volume-title":"Graph Drawing","author":"\u00c9.C. Verdi\u00e8re de","year":"2004","unstructured":"de Verdi\u00e8re, \u00c9.C., Lazarus, F.: Optimal pants decompositions and shortest homotopic cycles on an orientable surface. In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 478\u2013490. Springer, Heidelberg (2004)"},{"key":"14_CR8","unstructured":"Eppstein, D.: Dynamic generators of topologically embedded graphs. In: SODA 2003, pp. 599\u2013608 (2003)"},{"key":"14_CR9","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.\u00a031, 37\u201359 (2004); Preliminary version in SoCG 2002","journal-title":"Discrete Comput. Geom."},{"key":"14_CR10","unstructured":"Erickson, J., Whittlesey, K.: Greedy optimal homotopy and homology generators. In: SODA 2005 (2005)"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S.: Planar graphs, negative weight edges, shortest paths, and near linear time. In: FOCS 2001, pp. 232\u2013242 (2001)","DOI":"10.1109\/SFCS.2001.959897"},{"key":"14_CR12","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM\u00a034, 596\u2013615 (1987); Preliminary version in FOCS 1984","journal-title":"J. ACM"},{"key":"14_CR13","volume-title":"Algebraic Topology","author":"A. Hatcher","year":"2001","unstructured":"Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2001)"},{"issue":"1","key":"14_CR14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"M. Henzinger","year":"1997","unstructured":"Henzinger, M., Klein, P., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci.\u00a055(1), 3\u201323 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR15","unstructured":"Klein, P.N.: Multiple-source shortest paths in planar graphs. In: SODA 2005 (2005)"},{"key":"14_CR16","doi-asserted-by":"crossref","unstructured":"Lazarus, F., Pocchiola, M., Vegter, G., Verroust, A.: Computing a canonical polygonal schema of an orientable triangulated surface. In: SOCG 2001, pp. 80\u201389 (2001)","DOI":"10.1145\/378583.378630"},{"key":"14_CR17","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 University Press, Baltimore (2001)"},{"key":"14_CR18","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0095-8956(91)90009-9","volume":"51","author":"A. Schrijver","year":"1991","unstructured":"Schrijver, A.: Disjoint circuits of prescribed homotopies in a graph on a compact surface. J. Combin. Theory Ser. B\u00a051, 127\u2013159 (1991)","journal-title":"J. Combin. Theory Ser. B"},{"key":"14_CR19","first-page":"381","volume-title":"First European Congress of Mathematics, Progr. Math.","author":"A. Schrijver","year":"1994","unstructured":"Schrijver, A.: Paths in graphs and curves on surfaces. In: First European Congress of Mathematics, Progr. Math., vol. II, 120, pp. 381\u2013406. Birkh\u00e4user, Basel (1994)"},{"key":"14_CR20","doi-asserted-by":"publisher","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. Combin. Theory, Ser. B\u00a048, 155\u2013177 (1990)","journal-title":"J. Combin. Theory, Ser. B"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Vegter, G., Yap, C.K.: Computational complexity of combinatorial surfaces. In: SOCG 1990, pp. 102\u2013111 (1990)","DOI":"10.1145\/98524.98546"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11561071_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T20:09:38Z","timestamp":1736021378000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11561071_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540291183","9783540319511"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11561071_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}