{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:01Z","timestamp":1740109561594,"version":"3.37.3"},"reference-count":77,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T00:00:00Z","timestamp":1606694400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T00:00:00Z","timestamp":1606694400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1408763"],"award-info":[{"award-number":["1408763"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s00454-020-00255-3","type":"journal-article","created":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T17:25:03Z","timestamp":1606757103000},"page":"1253-1294","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Topologically Trivial Closed Walks in Directed Surface Graphs"],"prefix":"10.1007","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5253-2282","authenticated-orcid":false,"given":"Jeff","family":"Erickson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yipu","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,30]]},"reference":[{"issue":"2","key":"255_CR1","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1090\/S0002-9947-1928-1501429-1","volume":"30","author":"JW Alexander","year":"1928","unstructured":"Alexander, J.W.: Topological invariants of knots and links. Trans. Am. Math. Soc. 30(2), 275\u2013306 (1928)","journal-title":"Trans. Am. Math. Soc."},{"key":"255_CR2","doi-asserted-by":"crossref","unstructured":"Arge, L., Toma, L., Zeh, N.: I\/O-efficient topological sorting of planar DAGs. In: 15th Annual ACM Symposium on Parallelism in Algorithms and Architectures (San Diego 2003), pp. 85\u201393. ACM, New York (2003)","DOI":"10.1145\/777412.777427"},{"issue":"3","key":"255_CR3","doi-asserted-by":"crossref","first-page":"809","DOI":"10.1137\/S0097539798337716","volume":"30","author":"Ch Barrett","year":"2000","unstructured":"Barrett, Ch., Jacob, R., Marathe, M.: Formal-language-constrained path problems. SIAM J. Comput. 30(3), 809\u2013837 (2000)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"255_CR4","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1051\/ita\/2009011","volume":"43","author":"PG Bradford","year":"2009","unstructured":"Bradford, P.G., Thomas, D.A.: Labeled shortest paths in digraphs with negative and positive edge weights. Theor. Inform. Appl. 43(3), 567\u2013583 (2009)","journal-title":"Theor. Inform. Appl."},{"issue":"1","key":"255_CR5","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1006\/ciun.1994.1007","volume":"59","author":"JW Brandt","year":"1994","unstructured":"Brandt, J.W.: Convergence and continuity criteria for discrete approximations of the continuous planar skeleton. CVGIP: Image Underst. 59(1), 116\u2013124 (1994)","journal-title":"CVGIP: Image Underst."},{"issue":"2","key":"255_CR6","doi-asserted-by":"crossref","first-page":"#\u00a024","DOI":"10.1145\/1721837.1721840","volume":"6","author":"S Cabello","year":"2010","unstructured":"Cabello, S.: Finding shortest contractible and shortest separating cycles in embedded graphs. ACM Trans. Algorithms 6(2), #\u00a024 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"255_CR7","doi-asserted-by":"crossref","first-page":"1542","DOI":"10.1137\/120864271","volume":"42","author":"S Cabello","year":"2013","unstructured":"Cabello, S., Chambers, E.W., Erickson, J.: Multiple-source shortest paths in embedded graphs. SIAM J. Comput. 42(4), 1542\u20131571 (2013)","journal-title":"SIAM J. Comput."},{"key":"255_CR8","doi-asserted-by":"crossref","unstructured":"Cabello, S., Colin de Verdi\u00e8re, \u00c9., Lazarus, F.: Finding shortest non-trivial cycles in directed graphs on surfaces. In: 26th Annual Symposium on Computational Geometry (Snowbird 2010), pp. 156\u2013165. ACM, New York (2010)","DOI":"10.1145\/1810959.1810988"},{"issue":"4","key":"255_CR9","doi-asserted-by":"crossref","first-page":"1600","DOI":"10.1137\/100810794","volume":"25","author":"S Cabello","year":"2011","unstructured":"Cabello, S., Colin de Verdi\u00e8re, \u00c9.C., Lazarus, F.: Finding cycles with topological properties in embedded graphs. SIAM J. Discrete Math. 25(4), 1600\u20131614 (2011)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"255_CR10","first-page":"123","volume":"7","author":"S Cabello","year":"2016","unstructured":"Cabello, S., Colin de Verdi\u00e8re, \u00c9., Lazarus, F.: Finding shortest non-trivial cycles in directed graphs on surfaces. J. Comput. Geom. 7(1), 123\u2013148 (2016)","journal-title":"J. Comput. Geom."},{"issue":"4","key":"255_CR11","doi-asserted-by":"crossref","first-page":"#\u00a061","DOI":"10.1145\/1824777.1824781","volume":"6","author":"S Cabello","year":"2010","unstructured":"Cabello, S., Devos, M., Erickson, J., Mohar, B.: Finding one tight cycle. ACM Trans. Algorithms 6(4), #\u00a061 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"255_CR12","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(2), 213\u2013235 (2007)","journal-title":"Discrete Comput. Geom."},{"issue":"1\u20132","key":"255_CR13","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.comgeo.2007.10.010","volume":"41","author":"EW Chambers","year":"2008","unstructured":"Chambers, E.W., Colin de Verdi\u00e8re, \u00c9., Erickson, J., Lazarus, F., Whittlesey, K.: Splitting (complicated) surfaces is hard. Comput. Geom. 41(1\u20132), 94\u2013110 (2008)","journal-title":"Comput. Geom."},{"key":"255_CR14","doi-asserted-by":"crossref","unstructured":"Chambers, E.W., Erickson, J., Nayyeri, A.: Minimum cuts and shortest homologous cycles. In: 25th Annual Symposium on Computational Geometry (Aarhus 2009), pp. 377\u2013385. ACM, New York (2009)","DOI":"10.1145\/1542362.1542426"},{"issue":"6","key":"255_CR15","doi-asserted-by":"crossref","first-page":"1605","DOI":"10.1137\/090766863","volume":"41","author":"EW Chambers","year":"2012","unstructured":"Chambers, E.W., Erickson, J., Nayyeri, A.: Homology flows, cohomology cuts. SIAM J. Comput. 41(6), 1605\u20131634 (2012)","journal-title":"SIAM J. Comput."},{"key":"255_CR16","doi-asserted-by":"crossref","unstructured":"Chang, H.-C., Erickson, J., Letscher, D., de Mesmay, A., Schleimer, S., Sedgwick, E., Thurston, D., Tillmann, S.: Tightening curves on surfaces via local moves. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2018), pp. 121\u2013135. SIAM, Philadelphia (2018)","DOI":"10.1137\/1.9781611975031.8"},{"key":"255_CR17","doi-asserted-by":"crossref","unstructured":"Chang, H.-C., Erickson, J., Xu, C.: Detecting weakly simple polygons. In: 26th Annual ACM-SIAM Symposium on Discrete Algorithms (San Diego 2015), pp. 1655\u20131670. SIAM, Philadelphia (2015)","DOI":"10.1137\/1.9781611973730.110"},{"key":"255_CR18","doi-asserted-by":"crossref","unstructured":"Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vax\u00e8s, Y.: Diameters, centers, and approximating trees of $$\\delta $$-hyperbolic geodesic spaces and graphs. In: 24th Annual Symposium on Computational Geometry (College Park 2008), pp. 59\u201368. ACM, New York (2008)","DOI":"10.1145\/1377676.1377687"},{"issue":"4","key":"255_CR19","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1145\/153724.153727","volume":"40","author":"E Cohen","year":"1993","unstructured":"Cohen, E., Megiddo, N.: Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs. J. Assoc. Comput. Mach. 40(4), 791\u2013830 (1993)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"8","key":"255_CR20","doi-asserted-by":"crossref","first-page":"3784","DOI":"10.1137\/090761653","volume":"39","author":"\u00c9 Colin de Verdi\u00e8re","year":"2010","unstructured":"Colin de Verdi\u00e8re, \u00c9., Erickson, J.: Tightening nonsimple paths and cycles on surfaces. SIAM J. Comput. 39(8), 3784\u20133813 (2010)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"255_CR21","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1007\/BF03322926","volume":"1","author":"L Collatz","year":"1978","unstructured":"Collatz, L.: Spektren periodischer Graphen. Results Math. 1(1\u20132), 42\u201353 (1978)","journal-title":"Results Math."},{"issue":"1","key":"255_CR22","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/BF01456932","volume":"71","author":"M Dehn","year":"1911","unstructured":"Dehn, M.: \u00dcber unendliche diskontinuierliche Gruppen. Math. Ann. 71(1), 116\u2013144 (1911)","journal-title":"Math. Ann."},{"issue":"3","key":"255_CR23","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/BF01456725","volume":"72","author":"M Dehn","year":"1912","unstructured":"Dehn, M.: Transformation der Kurven auf zweiseitigen Fl\u00e4chen. Math. Ann. 72(3), 413\u2013421 (1912)","journal-title":"Math. Ann."},{"key":"255_CR24","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4668-8","volume-title":"Papers on Group Theory and Topology","author":"M Dehn","year":"1987","unstructured":"Dehn, M.: Papers on Group Theory and Topology. Springer, New York (1987)"},{"key":"255_CR25","unstructured":"Despr\u00e9, V., Lazarus, F.: Computing the geometric intersection number of curves. In: 33rd International Symposium on Computational Geometry. Leibniz Int. Proc. Inform., vol.\u00a077, #\u00a035. Leibniz-Zent. Inform., Wadern (2017)"},{"issue":"2","key":"255_CR26","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1006\/jcss.1998.1619","volume":"58","author":"TK Dey","year":"1999","unstructured":"Dey, T.K., Guha, S.: Transforming curves on surfaces. J. Comput. Syst. Sci. 58(2), 297\u2013325 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"255_CR27","volume-title":"Computational Topology. An Introduction","author":"H Edelsbrunner","year":"2010","unstructured":"Edelsbrunner, H., Harer, J.L.: Computational Topology. An Introduction. American Mathematical Society, Providence (2010)"},{"issue":"2","key":"255_CR28","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. Assoc. Comput. Mach. 19(2), 248\u2013264 (1972)","journal-title":"J. Assoc. Comput. Mach."},{"key":"255_CR29","unstructured":"Eppstein, D.: Dynamic generators of topologically embedded graphs. In: 14th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore 2003), pp. 599\u2013608. ACM, New York (2003)"},{"key":"255_CR30","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02392203","volume":"115","author":"DBA Epstein","year":"1966","unstructured":"Epstein, D.B.A.: Curves on $$2$$-manifolds and isotopies. Acta Math. 115, 83\u2013107 (1966)","journal-title":"Acta Math."},{"key":"255_CR31","doi-asserted-by":"crossref","unstructured":"Erickson, J.: Shortest non-trivial cycles in directed surface graphs. In: 27th Annual Symposium on Computational Geometry (Paris 2011), pp. 236\u2013243. ACM, New York (2011)","DOI":"10.1145\/1998196.1998231"},{"key":"255_CR32","doi-asserted-by":"crossref","unstructured":"Erickson, J., Fox, K., Lkhamsuren, L.: Holiest minimum-cost paths and flows in surface graphs. In: 50th Annual ACM SIGACT Symposium on Theory of Computing (Los Angeles 2018), pp. 1319\u20131332. ACM, New York (2018)","DOI":"10.1145\/3188745.3188904"},{"issue":"1","key":"255_CR33","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":"255_CR34","doi-asserted-by":"crossref","unstructured":"Erickson, J., Nayyeri, A.: Minimum cuts and shortest non-separating cycles via homology covers. In: 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco 2011), pp. 1166\u20131176. SIAM, Philadelphia (2011)","DOI":"10.1137\/1.9781611973082.88"},{"key":"255_CR35","doi-asserted-by":"crossref","unstructured":"Erickson, J., Wang, Y.: Topologically trivial closed walks in directed surface graphs. In: 35th International Symposium on Computational Geometry. Leibniz Int. Proc. Inform., vol.\u00a0129, #\u00a034. Leibniz-Zent. Inform., Wadern (2019)","DOI":"10.1007\/s00454-020-00255-3"},{"key":"255_CR36","doi-asserted-by":"crossref","unstructured":"Erickson, J., Whittlesey, K.: Transforming curves on surfaces redux. In: 24th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2013), pp. 1646\u20131655. SIAM, Philadelphia (2013)","DOI":"10.1137\/1.9781611973105.118"},{"issue":"1","key":"255_CR37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01405088","volume":"88","author":"WJ Floyd","year":"1987","unstructured":"Floyd, W.J., Plotnick, S.P.: Growth functions on Fuchsian groups and the Euler characteristic. Invent. Math. 88(1), 1\u201329 (1987)","journal-title":"Invent. Math."},{"key":"255_CR38","doi-asserted-by":"crossref","unstructured":"Fox, K.: Shortest non-trivial cycles in directed and undirected surface graphs. In: 24th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2013), pp. 352\u2013364. SIAM, Philadelphia (2013)","DOI":"10.1137\/1.9781611973105.26"},{"issue":"2","key":"255_CR39","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1007\/BF01233430","volume":"102","author":"SM Gersten","year":"1990","unstructured":"Gersten, S.M., Short, H.B.: Small cancellation theory and automatic groups. Invent. Math. 102(2), 305\u2013334 (1990)","journal-title":"Invent. Math."},{"key":"255_CR40","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511779534","volume-title":"Graphs, Surfaces and Homology","author":"P Giblin","year":"2010","unstructured":"Giblin, P.: Graphs, Surfaces and Homology. Cambridge University Press, Cambridge (2010)"},{"issue":"4","key":"255_CR41","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"AV Goldberg","year":"1988","unstructured":"Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum-flow problem. J. Assoc. Comput. Mach. 35(4), 921\u2013940 (1988)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1","key":"255_CR42","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF02471762","volume":"3","author":"R Grigorchuk","year":"1997","unstructured":"Grigorchuk, R., de la Harpe, P.: On problems related to growth, entropy, and spectrum in group theory. J. Dynam. Control Syst. 3(1), 51\u201389 (1997)","journal-title":"J. Dynam. Control Syst."},{"key":"255_CR43","doi-asserted-by":"crossref","unstructured":"Gromov, M.: Hyperbolic groups. In: Essays in Group Theory. Math. Sci. Res. Inst. Publ., vol. 8, pp. 75\u2013263. Springer, New York (1987)","DOI":"10.1007\/978-1-4613-9586-7_3"},{"issue":"1\u20132","key":"255_CR44","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1007\/BF02772960","volume":"51","author":"J Hass","year":"1985","unstructured":"Hass, J., Scott, P.: Intersections of curves on surfaces. Isr. J. Math. 51(1\u20132), 90\u2013120 (1985)","journal-title":"Isr. J. Math."},{"key":"255_CR45","volume-title":"Algebraic Topology","author":"A Hatcher","year":"2002","unstructured":"Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)"},{"key":"255_CR46","unstructured":"Iwano, K.: Two-Dimensional Dynamic Graphs and their VLSI Applications. PhD thesis, Princeton University (1987)"},{"key":"255_CR47","doi-asserted-by":"crossref","unstructured":"Iwano, K., Steiglitz, K.: Testing for cycles in infinite graphs with periodic structure. In: 19th Annual ACM Symposium on Theory of Computing (New York 1987), pp. 46\u201355. ACM, New York (1987)","DOI":"10.1145\/28395.28401"},{"issue":"5","key":"255_CR48","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1137\/0219061","volume":"19","author":"K Iwano","year":"1990","unstructured":"Iwano, K., Steiglitz, K.: A semiring on convex polygons and zero-sum cycle problems. SIAM J. Comput. 19(5), 883\u2013901 (1990)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"255_CR49","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0222032","volume":"22","author":"M-Y Kao","year":"1993","unstructured":"Kao, M.-Y.: Linear-processor NC algorithms for planar directed graphs I: strongly connected components. SIAM J. Comput. 22(3), 431\u2013459 (1993)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"255_CR50","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1016\/0022-0000(93)90042-U","volume":"47","author":"M-Y Kao","year":"1993","unstructured":"Kao, M.-Y., Klein, P.N.: Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs. J. Comput. Syst. Sci. 47(3), 459\u2013500 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"255_CR51","doi-asserted-by":"crossref","unstructured":"Kao, M.-Y., Shannon, G.E.: Local reorientation, global order, and planar topology. In: 21st Annual ACM Symposium on Theory of Computing (Seattle 1989), pp. 286\u2013296. ACM, New York (1989)","DOI":"10.1145\/73007.73034"},{"issue":"3","key":"255_CR52","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1137\/0222033","volume":"22","author":"M-Y Kao","year":"1993","unstructured":"Kao, M.-Y., Shannon, G.E.: Linear-processor NC algorithms for planar directed graphs II: directed spanning trees. SIAM J. Comput. 22(3), 460\u2013481 (1993)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"255_CR53","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1145\/321406.321418","volume":"14","author":"RM Karp","year":"1967","unstructured":"Karp, R.M., Miller, R.E., Winograd, S.: The organization of computations for uniform recurrence equations. J. Assoc. Comput. Mach. 14(3), 563\u2013590 (1967)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"255_CR54","doi-asserted-by":"crossref","first-page":"#\u00a030","DOI":"10.1145\/1721837.1721846","volume":"6","author":"PN Klein","year":"2010","unstructured":"Klein, P.N., Mozes, S., Weimann, O.: Shortest paths in directed planar graphs with negative lengths: a linear-space $$O(n\\log ^2 n)$$-time algorithm. ACM Trans. Algorithms 6(2), #\u00a030 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"255_CR55","doi-asserted-by":"crossref","unstructured":"Kosaraju, S.R., Sullivan, G.F.: Detecting cycles in dynamic graphs in polynomial time (preliminary version). In: 20th Annual ACM Symposium on Theory of Computing (Chicago 1988), pp. 398\u2013406. ACM, New York (1988)","DOI":"10.1145\/62212.62251"},{"key":"255_CR56","doi-asserted-by":"crossref","unstructured":"Kutz, M.: Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time. In: 22nd Annual Symposium on Computational Geometry (Sedona 2006), pp. 430\u2013438. ACM, New York (2006)","DOI":"10.1145\/1137856.1137919"},{"key":"255_CR57","doi-asserted-by":"crossref","unstructured":"Lazarus, F., Rivaud, J.: On the homotopy test on surfaces. In: IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 440\u2013449. IEEE Computer Soc., Los Alamitos (2012)","DOI":"10.1109\/FOCS.2012.12"},{"key":"255_CR58","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61896-3","volume-title":"Combinatorial Group Theory. Classics in Mathematics","author":"RC Lyndon","year":"2001","unstructured":"Lyndon, R.C., Schupp, P.E.: Combinatorial Group Theory. Classics in Mathematics. Springer, Berlin (2001)"},{"key":"255_CR59","unstructured":"M\u00f6bius, A.F.: \u00dcber der Bestimmung des Inhaltes eines Polyeders. Berichte \u00fcber die Verhandlungen der K\u00f6niglich S\u00e4chsischen Gesellschaft der Wissenschaften zu Leipzig, Math.-Phys. Cl. 17, 31\u201368 (1865)"},{"issue":"1","key":"255_CR60","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4310\/jdg\/1214501132","volume":"2","author":"J Milnor","year":"1968","unstructured":"Milnor, J.: A note on curvature and fundamental group. J. Differ. Geom. 2(1), 1\u20137 (1968)","journal-title":"J. Differ. Geom."},{"key":"255_CR61","volume-title":"Graphs on Surfaces. Johns Hopkins Studies in the Mathematical Sciences","author":"B Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2001)"},{"issue":"1\u20133","key":"255_CR62","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/S0012-365X(96)00102-1","volume":"173","author":"JF Moran","year":"1997","unstructured":"Moran, J.F.: The growth rate and balance of homogeneous tilings in the hyperbolic plane. Discrete Math. 173(1\u20133), 151\u2013186 (1997)","journal-title":"Discrete Math."},{"key":"255_CR63","doi-asserted-by":"crossref","unstructured":"Mozes, S., Nikolaev, K., Nussbaum, Y., Weimann, O.: Minimum cut of directed planar graphs in $$O(n\\log \\log n)$$ time. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2018), pp. 477\u2013494. SIAM, Philadelphia (2018)","DOI":"10.1137\/1.9781611975031.32"},{"key":"255_CR64","doi-asserted-by":"crossref","unstructured":"Mozes, S., Wulff-Nilsen, Ch.: Shortest paths in planar graphs with real lengths in $$O(n\\log ^2 n\/\\log \\log n)$$ time. In: Algorithms\u2014ESA 2010 (18th Annual European Symposium on Algorithms (Liverpool 2010)). Part II. Lecture Notes in Comput. Sci., vol. 6347, pp. 206\u2013217. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-15781-3_18"},{"issue":"3","key":"255_CR65","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0022-0000(83)90003-X","volume":"26","author":"DE Muller","year":"1983","unstructured":"Muller, D.E., Schupp, P.E.: Groups, the theory of ends, and context-free languages. J. Comput. Syst. Sci. 26(3), 295\u2013310 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"255_CR66","doi-asserted-by":"crossref","first-page":"349","DOI":"10.2140\/agt.2001.1.349","volume":"1","author":"M Neumann-Coto","year":"2001","unstructured":"Neumann-Coto, M.: A characterization of shortest geodesics on surfaces. Algebr. Geom. Topol. 1, 349\u2013368 (2001)","journal-title":"Algebr. Geom. Topol."},{"key":"255_CR67","doi-asserted-by":"crossref","unstructured":"Orlin, J.B.: Some problems on dynamic\/periodic graphs. In: Progress in Combinatorial Optimization (Waterloo 1982), pp. 273\u2013293. Academic Press, Toronto (1984)","DOI":"10.1016\/B978-0-12-566780-7.50022-2"},{"key":"255_CR68","unstructured":"Papadimitriou, Ch.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover, Mineola (1998)"},{"issue":"4","key":"255_CR69","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0020-0190(79)90023-1","volume":"8","author":"J Plesn\u00edk","year":"1979","unstructured":"Plesn\u00edk, J.: The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Inf. Process. Lett. 8(4), 199\u2013201 (1979)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"255_CR70","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/BF01293266","volume":"11","author":"V Ramachandran","year":"1994","unstructured":"Ramachandran, V., Yang, H.: Finding the closed partition of a planar graph. Algorithmica 11(5), 443\u2013468 (1994)","journal-title":"Algorithmica"},{"issue":"3","key":"255_CR71","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1109\/5.4402","volume":"76","author":"SK Rao","year":"1988","unstructured":"Rao, S.K., Kailath, T.: Regular iterative algorithms and their implementation on processor arrays. Proc. IEEE 76(3), 259\u2013269 (1988)","journal-title":"Proc. IEEE"},{"issue":"3","key":"255_CR72","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"255_CR73","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1007\/BF01070252","volume":"12","author":"LB Smikun","year":"1976","unstructured":"Smikun, L.B.: Connection between context-free groups and groups with decidable problems of automata equivalence. Cybernetics 12(5), 687\u2013691 (1976)","journal-title":"Cybernetics"},{"issue":"2","key":"255_CR74","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"},{"issue":"2","key":"255_CR75","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1002\/net.3230010206","volume":"1","author":"N Tomizawa","year":"1971","unstructured":"Tomizawa, N.: On some techniques useful for solution of transportation network problems. Networks 1(2), 173\u2013194 (1971)","journal-title":"Networks"},{"issue":"2","key":"255_CR76","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1145\/321386.321392","volume":"14","author":"WM Waite","year":"1967","unstructured":"Waite, W.M.: Path detection in multidimensional iterative arrays. J. Assoc. Comput. Mach. 14(2), 300\u2013310 (1967)","journal-title":"J. Assoc. Comput. Mach."},{"key":"255_CR77","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Graph-theoretic methods in database theory. In: 9th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (Nashville 1990), pp. 230\u2013242. ACM, New York (1990)","DOI":"10.1145\/298514.298576"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00255-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-020-00255-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00255-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,3]],"date-time":"2020-12-03T15:03:00Z","timestamp":1607007780000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-020-00255-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,30]]},"references-count":77,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["255"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00255-3","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2020,11,30]]},"assertion":[{"value":"15 September 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 May 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 November 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}