{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T11:23:36Z","timestamp":1758281016945},"reference-count":81,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"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":[[2013,6]]},"DOI":"10.1007\/s00454-013-9515-z","type":"journal-article","created":{"date-parts":[[2013,6,14]],"date-time":"2013-06-14T13:00:18Z","timestamp":1371214818000},"page":"823-863","source":"Crossref","is-referenced-by-count":7,"title":["Tracing Compressed Curves in Triangulated Surfaces"],"prefix":"10.1007","volume":"49","author":[{"given":"Jeff","family":"Erickson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amir","family":"Nayyeri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,6,15]]},"reference":[{"issue":"9","key":"9515_CR1","doi-asserted-by":"crossref","first-page":"3821","DOI":"10.1090\/S0002-9947-05-03919-X","volume":"358","author":"I Agol","year":"2006","unstructured":"Agol, I., Hass, J., Thurston, W.P.: The computational complexity of knot genus and spanning area. Trans. Am. Math. Soc. 358(9), 3821\u20133850 (2006)","journal-title":"Trans. Am. Math. Soc."},{"key":"9515_CR2","unstructured":"Alexandrov, A.D.: Existence of a convex polyhedron and of a convex surface with a given metric. Rec. Math. [Mat. Sbornik] 11(53)(1\u20132), 15\u201365 (1942). In Russian, with English summary"},{"key":"9515_CR3","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/BF01952419","volume":"2","author":"D Avis","year":"1986","unstructured":"Avis, D., Gum, T., Toussaint, G.T.: Visiblity between two edges of a simple polygon. Vis. Comput. 2, 342\u2013357 (1986)","journal-title":"Vis. Comput."},{"key":"9515_CR4","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/0020-0190(76)90071-5","volume":"5","author":"JL Bentley","year":"1976","unstructured":"Bentley, J.L., Yao, A.C.C.: An almost optimal algorithm for unbounded searching. Inf. Proc. Lett. 5, 82\u201387 (1976)","journal-title":"Inf. Proc. Lett."},{"issue":"2","key":"9515_CR5","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0040-9383(85)90056-4","volume":"24","author":"JS Birman","year":"1985","unstructured":"Birman, J.S., Series, C.: Geodesics with bounded intersection number on surfaces are sparsely distributed. Topology 24(2), 217\u2013225 (1985)","journal-title":"Topology"},{"key":"9515_CR6","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0022-4049(88)90094-1","volume":"52","author":"JS Birman","year":"1988","unstructured":"Birman, J.S., Series, C.: Algebraic linearity for an automorphism of a surface group. J. Pure Appl. Algebra 52, 227\u2013275 (1988)","journal-title":"J. Pure Appl. Algebra"},{"key":"9515_CR7","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1016\/j.comgeo.2011.05.006","volume":"44","author":"P Bose","year":"2011","unstructured":"Bose, P., Maheshwari, A., Shu, C., Wuhrer, S.: A survey of geodesic paths on 3D surfaces. Comput. Geom. Theory Appl. 44, 486\u2013498 (2011)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9515_CR8","unstructured":"Burago, Y.D., Zalgaller, V.A.: Isometric piecewise-linear embeddings of two-dimensional manifolds with a polyhedral metric into $$\\mathbb{R}^3$$ R 3 . Algebra i Analiz 7(3), 76\u201395 (1995). In Russian. English translation in [9]"},{"key":"9515_CR9","unstructured":"Burago, Y.D., Zalgaller, V.A.: Isometric piecewise-linear embeddings of two-dimensional manifolds with a polyhedral metric into $$\\mathbb{R}^3$$ R 3 . St. Petersburg Math. J. 7(3), 369\u2013385 (1996). English translation of [8]"},{"key":"9515_CR10","doi-asserted-by":"crossref","unstructured":"Burton, B.A.: The complexity of the normal surface solution space. In: Proceedings of the 26th Annual Symposium Computational Geometry, pp. 201\u2013209 (2010)","DOI":"10.1145\/1810959.1810995"},{"key":"9515_CR11","doi-asserted-by":"crossref","unstructured":"Burton, B.A., Ozlen, M.: Computing the crosscap number of a knot using integer programming and normal surfaces. ACM Trans. Math. Software 39(1) (2012)","DOI":"10.1145\/2382585.2382589"},{"key":"9515_CR12","doi-asserted-by":"crossref","unstructured":"Chazelle, B.: A theorem on polygon cutting with applications. In: Proceedings of 23rd Annual IEEE Symposium Foundations of Computer Science, pp. 339\u2013349 (1982)","DOI":"10.1109\/SFCS.1982.58"},{"key":"9515_CR13","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/BF02187747","volume":"4","author":"B Chazelle","year":"1989","unstructured":"Chazelle, B., Guibas, L.J.: Visibility and intersection problems in plane geometry. Discrete Comput. Geom. 4, 551\u2013581 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"9515_CR14","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1142\/S0218195996000095","volume":"6","author":"J Chen","year":"1996","unstructured":"Chen, J., Han, Y.: Shortest paths on a polyhedron, part I: computing shortest paths. Int. J. Comput. Geom. Appl. 6(2), 127\u2013144 (1996)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9515_CR15","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/BF02547712","volume":"69","author":"M Dehn","year":"1938","unstructured":"Dehn, M.: Die Gruppe der Abbildungsklassen (Das arithmetische Feld auf Fl\u00e4chen). Acta Mathematica 69, 135\u2013206 (1938)","journal-title":"Acta Mathematica"},{"key":"9515_CR16","volume-title":"Ordering Braids, Mathematical Surveys and Monographs, vol. 148","author":"P Dehornoy","year":"2008","unstructured":"Dehornoy, P., Dynnikov, I., Rolfsen, D., Wiest, B.: Ordering Braids, Mathematical Surveys and Monographs, vol. 148. American Mathematical Society, Providence (2008)"},{"key":"9515_CR17","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511735172","volume-title":"Geometric Folding Algorithms: Linkages, Origami. Polyhedra","author":"ED Demaine","year":"2007","unstructured":"Demaine, E.D., O\u2019Rourke, J.: Geometric Folding Algorithms: Linkages, Origami. Polyhedra. Cambridge University Press, Cambridge (2007)"},{"key":"9515_CR18","doi-asserted-by":"crossref","unstructured":"Diekert, V., Kufleitner, M.: A remark about quadratic trace equations. In: Proceedings of 6th International Conference on Development and Language Theory. Lecture Notes in Computer Science, vol. 2450, pp. 59\u201366. Springer, Berlin (2003)","DOI":"10.1007\/3-540-45005-X_5"},{"issue":"4","key":"9515_CR19","doi-asserted-by":"crossref","first-page":"801","DOI":"10.4171\/JEMS\/98","volume":"9","author":"I Dynnikov","year":"2007","unstructured":"Dynnikov, I., Wiest, B.: On the complexity of braids. J. Eur. Math. Soc. 9(4), 801\u2013840 (2007)","journal-title":"J. Eur. Math. Soc."},{"key":"9515_CR20","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)"},{"key":"9515_CR21","unstructured":"Ellison, H.: The city on the edge of forever. Star Trek, season 1, episode 28 (1967)"},{"key":"9515_CR22","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 Mathematica 115, 83\u2013107 (1966)","journal-title":"Acta Mathematica"},{"issue":"1","key":"9515_CR23","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":"9515_CR24","doi-asserted-by":"crossref","unstructured":"Erickson, J., Nayyeri, A.: Tracing compressed curves in triangulated surfaces. In: Proceedings of 28th Annual Symposium on Computational Geometry, pp. 131\u2013140 (2012)","DOI":"10.1145\/2261250.2261270"},{"key":"9515_CR25","unstructured":"Fathi, A., Laudenbach, F., Po\u00e9naru, V.: Travaux de Thurston sur les surfaces, Ast\u00e9risque, vol. 66\u201367. Soc. Math. de France (1979). S\u00e9minaire Orsay. English translation in [26]"},{"key":"9515_CR26","unstructured":"Fathi, A., Laudenbach, F., Po\u00e9naru, V.: Thurston\u2019s Work on Surfaces. Mathematical Notes. Princeton University Press (2011). Translated by Djun Kim and Dan Margalit. English translation of [25]"},{"key":"9515_CR27","doi-asserted-by":"crossref","unstructured":"G\u0105sieniec, L., Karpinski, M., Plandowski, W., Rytter, W.: Efficient algorithms for Lempel-Ziv encoding. In: Karlsson, R., Lingas, A. (eds.) Proceedings of 8th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, vol. 1097, pp. 392\u2013403. Springer, Berlin (1996)","DOI":"10.1007\/3-540-61422-2_148"},{"key":"9515_CR28","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/BF02559591","volume":"105","author":"W Haken","year":"1961","unstructured":"Haken, W.: Theorie der Normalfl\u00e4chen: Ein Isotopiekriterium f\u00fcr den Kreisknoten. Acta Mathematica 105, 245\u2013375 (1961)","journal-title":"Acta Mathematica"},{"issue":"2","key":"9515_CR29","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1145\/301970.301971","volume":"46","author":"J Hass","year":"1999","unstructured":"Hass, J., Lagarias, J.C., Pippenger, N.: The computational complexity of knot and link problems. J. ACM 46(2), 185\u2013211 (1999)","journal-title":"J. ACM"},{"issue":"2","key":"9515_CR30","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1002\/mana.200510597","volume":"281","author":"F Herrlich","year":"2008","unstructured":"Herrlich, F., Schmith\u00fcsen, G.: An extraordinary origami curve. Math. Nachr. 281(2), 219\u2013237 (2008)","journal-title":"Math. Nachr."},{"key":"9515_CR31","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0925-7721(94)90010-8","volume":"4","author":"J Hershberger","year":"1994","unstructured":"Hershberger, J., Snoeyink, J.: Computing minimum length paths of a given homotopy class. Comput. Geom. Theory Appl. 4, 63\u201398 (1994)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"3","key":"9515_CR32","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1006\/jagm.1995.1017","volume":"18","author":"J Hershberger","year":"1995","unstructured":"Hershberger, J., Suri, S.: A pedestrian approach to ray shooting: shoot a ray, take a walk. J. Algorithms 18(3), 403\u2013431 (1995)","journal-title":"J. Algorithms"},{"key":"9515_CR33","unstructured":"Hirsch, M.W.: Differential Topology. Graduate Texts in Mathematics, vol. 33. Springer, New York (1997)"},{"key":"9515_CR34","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Addison-Wesley, Boston (2006)"},{"key":"9515_CR35","doi-asserted-by":"crossref","unstructured":"Jaco, W., Letscher, D., Rubinstein, J.H.: Algorithms for essential surfaces in 3-manifolds. In: Berrick, A.J., Leung, M.C., Xu, X. (eds.) Topology and Geometry: Commemorating SISTAG. Contemporary Mathematics, vol. 314, pp. 107\u2013124. American Mathematical Society, Providence (2002)","DOI":"10.1090\/conm\/314\/05426"},{"key":"9515_CR36","doi-asserted-by":"crossref","first-page":"61","DOI":"10.4310\/jdg\/1090503053","volume":"65","author":"W Jaco","year":"2003","unstructured":"Jaco, W., Rubinstein, J.H.: 0-efficient triangulations of 3-manifolds. J. Diff. Geom. 65, 61\u2013168 (2003)","journal-title":"J. Diff. Geom."},{"key":"9515_CR37","first-page":"172","volume":"4","author":"M Karpinski","year":"1997","unstructured":"Karpinski, M., Rytter, W., Shinohara, A.: An efficient pattern-matching algorithm for strings with short descriptions. Nordic J. Comput. 4, 172\u2013186 (1997)","journal-title":"Nordic J. Comput."},{"issue":"3","key":"9515_CR38","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1109\/18.841160","volume":"46","author":"JC Kieffer","year":"2000","unstructured":"Kieffer, J.C., Yang, E.: Grammar based codes: a new class of universal lossless source codes. IEEE Trans. Inf. Theory 46(3), 737\u2013754 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9515_CR39","unstructured":"Klein, P.N.: Optimization Algorithms for Planar Graphs. Unpublished textbook draft (2012). http:\/\/planarity.org\/"},{"key":"9515_CR40","unstructured":"Kneser, H.: Geschlossene Fl\u00e4chen in dreidimensionalen Mannigfaltigkeiten. Jahresbericht Deutschen Math.-Verein. 38, 248\u2013260 (1930)"},{"key":"9515_CR41","unstructured":"Lam\u00e9, G.: Note sur la limite du monbre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers. Compt. Rend. Acad. Sci. Paris 19, 857\u2013870 (1844)"},{"key":"9515_CR42","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/net.3230140304","volume":"14","author":"DT Lee","year":"1984","unstructured":"Lee, D.T., Preparata, F.P.: Euclidean shortest paths in the presence of rectilinear barriers. Networks 14, 393\u2013410 (1984)","journal-title":"Networks"},{"key":"9515_CR43","unstructured":"l\u2019Huillier, S.A.J.: D\u00e9monstration imm\u00e9diate d\u2019un th\u00e9or\u00e8me fondamental d\u2019Euler sur les polyh\u00e8dres, et exception dont ce th\u00e9or\u00e8me est susceptible. M\u00e9moires de l\u2019Acad\u00e9mie Imp\u00e9riale des Sciences de Saint-Petersbourg 4, 271\u2013301 (1811)"},{"key":"9515_CR44","unstructured":"l\u2019Huillier, S.A.J.: M\u00e9moire sur la poly\u00e9drom\u00e9trie contenant une d\u00e9monstration directe du th\u00e9or\u00e8me d\u2019Euler sur les poly\u00e9dres, et un examen des diverses exceptions auxquelles ce th\u00e9or\u00e8me est assujetti. Annales de Math\u00e9matiques Pures et Appliqu\u00e9es [Annales de Gergonne] 3, 169\u2013189 (1813). Summarized by Joseph Diaz Gergonne"},{"key":"9515_CR45","unstructured":"Lifshits, Y.: Algorithms and complexity analysis for processing compressed texts. Ph.D. Thesis, Steklov Institute of Mathematics, St. Petersburg (2007). In Russian. http:\/\/logic.pdmi.ras.ru\/~yura\/papers\/lifshits2007thesis.pdf"},{"key":"9515_CR46","doi-asserted-by":"crossref","unstructured":"Lifshits, Y.: Processing Compressed Texts: A Tractabiliity Border. In: Proceedings of 18th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 4850, pp. 228\u2013240. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-73437-6_24"},{"key":"9515_CR47","unstructured":"Lyusternik, L.A.: Shortest Paths: Variational Problems. Popular Lectures in Mathematics, vol. 13. Pergamon Press, New York: Translated and adapted from the Russian by Collins, P., and Brown, R.B. (1964)"},{"key":"9515_CR48","unstructured":"Mitchell, J.: Geometric shortest paths and network optimization. In: Sack, J.R., Urrutia, J. (eds.) The Handbook of Computational Geometry, Chap. 15, pp. 633\u2013701. Elsevier Science, Amsterdam (2000). http:\/\/www.ams.sunysb.edu\/jsbm\/papers\/survey.ps.gz"},{"key":"9515_CR49","unstructured":"Miyazaki, M., Shinohara, A., Takeda, M.: An improved pattern matching algorithm for strings in terms of straight-line programs. J. Discrete Algorithms [Hermes] 1 (1), 187\u2013204 (2000)"},{"key":"9515_CR50","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1017\/S0143385700009585","volume":"2","author":"R Moeckel","year":"1982","unstructured":"Moeckel, R.: Geodesics on modular surfaces and continued fractions. Ergodic Theory Dynam. Sys. 2, 69\u201383 (1982)","journal-title":"Ergodic Theory Dynam. Sys."},{"key":"9515_CR51","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":"9515_CR52","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF02187877","volume":"2","author":"DM Mount","year":"1987","unstructured":"Mount, D.M.: Storing the subdivision of a polyhedral surface. Discrete Comput. Geom. 2, 153\u2013174 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"9515_CR53","unstructured":"Nuclear Monkey Software: Narbacular Drop. Video game (2005)"},{"issue":"4","key":"9515_CR54","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1007\/s00454-002-2891-4","volume":"28","author":"J Pach","year":"2001","unstructured":"Pach, J., T\u00f3th, G.: Recognizing string graphs is decidable. Discrete Comput. Geom. 28(4), 593\u2013606 (2001)","journal-title":"Discrete Comput. Geom."},{"key":"9515_CR55","first-page":"39","volume":"30","author":"RC Penner","year":"1984","unstructured":"Penner, R.C.: The action of the mapping class group on curves in surfaces. L\u2019Enseignment Math\u00e9matique 30, 39\u201355 (1984)","journal-title":"L\u2019Enseignment Math\u00e9matique"},{"key":"9515_CR56","doi-asserted-by":"crossref","DOI":"10.1515\/9781400882458","volume-title":"Combinatorics of Train Tracks. Annals of Mathematical Studies, vol. 125","author":"RC Penne","year":"1992","unstructured":"Penne, R.C., Harer, J.L.: Combinatorics of Train Tracks. Annals of Mathematical Studies, vol. 125. Princeton University Press, Princeton (1992)"},{"key":"9515_CR57","doi-asserted-by":"crossref","unstructured":"Plandowski, W., Rytter, W.: Application of Lempel-Ziv encodings to the solution of word equations. In: Proceedings of 25th International Conference Automata Language and Programming. Lecture Notes in Computer Science, vol. 1443, pp. 731\u2013742. Springer, Berlin (1998)","DOI":"10.1007\/BFb0055097"},{"key":"9515_CR58","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction. Texts and Monographs in Computer Science","author":"FP Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Texts and Monographs in Computer Science. Springer, Berlin (1985)"},{"key":"9515_CR59","doi-asserted-by":"crossref","unstructured":"Robson, J.M., Diekert, V.: On quadratic word equations. In: Proceedeings of 16th Annual Conference on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 1563, pp. 217\u2013226. Springer, Berlin (1999)","DOI":"10.1007\/3-540-49116-3_20"},{"key":"9515_CR60","doi-asserted-by":"crossref","unstructured":"Robson, J.M., Diekert, V.: Quadratic word equations. In: J. Karhum\u00e4ki, H.A. Maurer, G. Paun, G. Rozenberg (eds.) Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, pp. 314\u2013326. Springer, Berlin (1999)","DOI":"10.1007\/978-3-642-60207-8_28"},{"key":"9515_CR61","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci. 302, 211\u2013222 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9515_CR62","unstructured":"Saucan, E.: On a construction of Burago and Zalgaller. Asian J. Math. 16(4), 587\u2013606 (2012)"},{"key":"9515_CR63","doi-asserted-by":"crossref","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u010d, D.: Algorithms for normal curves and surfaces. In: Proceedings of 8th International Conference on Computing and Combinatorics. Lecture Notes in Computer Science, vol. 2387, pp. 370\u2013380. Springer, Berlin (2002)","DOI":"10.1007\/3-540-45655-4_40"},{"issue":"2","key":"9515_CR64","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/S0022-0000(03)00045-X","volume":"67","author":"M Schaefer","year":"2003","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u010d, D.: Recognizing string graphs in NP. J. Comput. Syst. Sci. 67(2), 365\u2013380 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"9515_CR65","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u010d, D.: Spiraling and folding: the topological view. In: Proceedings of 19th Annual Canadian Conference on Computational Geometry, pp. 73\u201376 (2007)"},{"key":"9515_CR66","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u010d, D.: Computing Dehn twists and geometric intersection numbers in polynomial time. In: Proceedings of 20th Canadian Conference on Computational Geometry, pp. 111\u2013114 (2008). Full version: Technical Report 05\u2013009, Computer Science Department, DePaul University. April 2005. http:\/\/facweb.cs.depaul.edu\/research\/techreports\/abstract05009.htm"},{"issue":"3","key":"9515_CR67","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1007\/s00453-009-9362-8","volume":"60","author":"M Schaefer","year":"2011","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u010d, D.: Spiraling and folding: the word view. Algorithmica 60(3), 609\u2013626 (2011)","journal-title":"Algorithmica"},{"key":"9515_CR68","unstructured":"Schleimer, S.: Sphere recognition lies in NP. Preprint (2004). ArXiv:math\/0407047"},{"issue":"1","key":"9515_CR69","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s00454-009-9136-8","volume":"43","author":"Y Schreiber","year":"2010","unstructured":"Schreiber, Y.: An optimal-time algorithm for shortest paths on realistic polyhedra. Discrete Comput. Geom. 43(1), 21\u201353 (2010)","journal-title":"Discrete Comput. Geom."},{"issue":"1\u20133","key":"9515_CR70","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1007\/s00454-007-9031-0","volume":"39","author":"Y Schreiber","year":"2008","unstructured":"Schreiber, Y., Sharir, M.: An optimal-time algorithm for shortest paths on a convex polytope in three dimensions. Discrete Comput. Geom. 39(1\u20133), 500\u2013579 (2008)","journal-title":"Discrete Comput. Geom."},{"key":"9515_CR71","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1112\/jlms\/s2-31.1.69","volume":"31","author":"C Series","year":"1985","unstructured":"Series, C.: The modular surface and continued fractions. J. Lond. Math. Soc. 31, 69\u201380 (1985)","journal-title":"J. Lond. Math. Soc."},{"issue":"4","key":"9515_CR72","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1017\/S0143385700003722","volume":"6","author":"C Series","year":"1986","unstructured":"Series, C.: Geometrical Markov coding of geodesics on surfaces of constant negative curvature. Ergodic Theory Dynam. Sys. 6(4), 601\u2013625 (1986)","journal-title":"Ergodic Theory Dynam. Sys."},{"key":"9515_CR73","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1006\/hmat.1994.1031","volume":"21","author":"J Shallit","year":"1994","unstructured":"Shallit, J.: Origins of the analysis of the Euclidean algorithm. Hist. Math. 21, 401\u2013419 (1994)","journal-title":"Hist. Math."},{"key":"9515_CR74","unstructured":"Sipser, M.: Introduction to the Theory of Computation. PWS Publishing, Boston (1997)"},{"key":"9515_CR75","unstructured":"\u0160tefankovi\u010d, D.: Algorithms for simple curves on surfaces, string graphs, and crossing numbers. Ph.D. Thesis, Department of Computer Science, University of Chicago, Chicago (2005). http:\/\/people.cs.uchicago.edu\/~laci\/students\/stefankovic-phd.pdf"},{"key":"9515_CR76","doi-asserted-by":"crossref","unstructured":"Stillwell, J.: Classical Topology and Combinatorial Group Theory, 2nd edn. Graduate Texts in Mathematics, vol. 72. Springer, Berlin (1993)","DOI":"10.1007\/978-1-4612-4372-4"},{"key":"9515_CR77","unstructured":"Thurston, W.P.: On the geometry and dynamics of diffeomorphisms of surfaces. Bull. Am. Math. Soc. 19(2), 417\u2013431 (1988). Circulated as a preprint in 1976"},{"issue":"3","key":"9515_CR78","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0167-8655(86)90015-2","volume":"4","author":"GT Toussaint","year":"1986","unstructured":"Toussaint, G.T.: Shortest path solves edge-to-edge visibility in a polygon. Pattern Recognit. Lett. 4(3), 165\u2013170 (1986)","journal-title":"Pattern Recognit. Lett."},{"key":"9515_CR79","unstructured":"Valve Corporation: Portal. Video game (2007)"},{"key":"9515_CR80","unstructured":"Valve Corporation: Portal 2. Video game (2011)"},{"key":"9515_CR81","unstructured":"Wachowski, A., Wachowski, L.: Matrix Revolutions. Warner Bros. (2003). Motion picture"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-013-9515-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-013-9515-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-013-9515-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,2]],"date-time":"2023-07-02T11:19:10Z","timestamp":1688296750000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-013-9515-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":81,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["9515"],"URL":"https:\/\/doi.org\/10.1007\/s00454-013-9515-z","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6]]}}}