{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:20:07Z","timestamp":1760440807737},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,12,12]],"date-time":"2008-12-12T00:00:00Z","timestamp":1229040000000},"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":[[2009,12]]},"DOI":"10.1007\/s00454-008-9125-3","type":"journal-article","created":{"date-parts":[[2008,12,11]],"date-time":"2008-12-11T17:19:43Z","timestamp":1229015983000},"page":"570-585","source":"Crossref","is-referenced-by-count":15,"title":["A Polynomial Bound for Untangling Geometric Planar\u00a0Graphs"],"prefix":"10.1007","volume":"42","author":[{"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[]},{"given":"Vida","family":"Dujmovi\u0107","sequence":"additional","affiliation":[]},{"given":"Ferran","family":"Hurtado","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Langerman","sequence":"additional","affiliation":[]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[]},{"given":"David R.","family":"Wood","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,12,12]]},"reference":[{"key":"9125_CR1","unstructured":"Abellanas, M., Hurtado, F., Ramos, P.: Tolerancia de arreglos de segmentos. In: Proc. VI Encuentros de Geometr\u00eda Computacional, pp.\u00a077\u201384 (1995)"},{"key":"9125_CR2","doi-asserted-by":"crossref","unstructured":"Cibulka, J.: Untangling polygons and graphs. In: Topological and Geometric Graph Theory. Electronic Notes in Discrete Mathematics, vol.\u00a031, pp.\u00a0207\u2013211 (2008)","DOI":"10.1016\/j.endm.2008.06.041"},{"issue":"1","key":"9125_CR3","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H. Fraysseix de","year":"1990","unstructured":"de Fraysseix, H., Pach, J., Pollac, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41\u201351 (1990)","journal-title":"Combinatorica"},{"issue":"2","key":"9125_CR4","doi-asserted-by":"crossref","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"R.P. Dilworth","year":"1950","unstructured":"Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math. 51(2), 161\u2013166 (1950)","journal-title":"Ann. Math."},{"key":"9125_CR5","first-page":"464","volume":"2","author":"P. Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 464\u2013470 (1935)","journal-title":"Compos. Math."},{"key":"9125_CR6","first-page":"229","volume":"11","author":"I. F\u00e1ry","year":"1948","unstructured":"F\u00e1ry, I.: On straight line representation of planar graphs. Acta Univ. Szeged. Sect. Sci. Math. 11, 229\u2013233 (1948)","journal-title":"Acta Univ. Szeged. Sect. Sci. Math."},{"key":"9125_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/978-3-540-77537-9_13","volume-title":"Proc. 15th International Symp. on Graph Drawing (GD\u201907)","author":"X. Goaoc","year":"2008","unstructured":"Goaoc, X., Kratochvil, J., Okamoto, Y., Shin, C.-S., Wolff, A.: Moving vertices to make drawings plane. In: Proc. 15th International Symp. on Graph Drawing (GD\u201907). Lecture Notes in Computer Science, vol.\u00a04875, pp.\u00a0101\u2013112. Springer, Berlin (2008). Also in http:\/\/arxiv.org\/abs\/0706.1002"},{"issue":"12","key":"9125_CR8","doi-asserted-by":"crossref","first-page":"2368","DOI":"10.1016\/j.dam.2007.10.012","volume":"156","author":"S.-H. Hong","year":"2008","unstructured":"Hong, S.-H., Nagamochi, H.: Convex drawings of graphs with non-convex boundary constraints. Discrete Appl. Math. 156(12), 2368\u20132380 (2008)","journal-title":"Discrete Appl. Math."},{"key":"9125_CR9","unstructured":"Kang, M., Pikhurko, O., Ravsky, A., Schacht, M., Verbitsky, O.: Obfuscated drawings of planar graphs (2008). http:\/\/arxiv.org\/abs\/0803.0858"},{"key":"9125_CR10","unstructured":"Kang, M., Schacht, M., Verbitsky, O.: How much work does it take to straighten a plane graph out? (2007). http:\/\/arxiv.org\/abs\/0707.3373"},{"issue":"4","key":"9125_CR11","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1007\/s00454-002-2889-y","volume":"28","author":"J. Pach","year":"2002","unstructured":"Pach, J., Tardos, G.: Untangling a polygon. Discrete Comput. Geom. 28(4), 585\u2013592 (2002)","journal-title":"Discrete Comput. Geom."},{"key":"9125_CR12","unstructured":"Ramos, P.: Tolerancia de estructuras geom\u00e9tricas y combinatorias. Ph.D. thesis, Universidad Polit\u00e9cnica de Madrid, Madrid, Spain (1995)"},{"key":"9125_CR13","unstructured":"Ravsky, A., Verbitsky, O.: On collinear sets in straight line drawings (2008). http:\/\/arxiv.org\/abs\/0806.0253"},{"key":"9125_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1007\/978-3-540-77566-9_41","volume-title":"Proc. 34th Internat. Conf. on Current Trends in Theory and Practice of Computer Science (SOFSEM\u201908)","author":"A. Spillner","year":"2008","unstructured":"Spillner, A., Wolff, A.: Untangling a planar graph. In: Proc. 34th Internat. Conf. on Current Trends in Theory and Practice of Computer Science (SOFSEM\u201908). Lecture Notes in Computer Science, vol.\u00a04910, pp.\u00a0473\u2013484. Springer, Berlin (2008). Also in http:\/\/arxiv.org\/abs\/0709.0170"},{"issue":"1\u20133","key":"9125_CR15","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1016\/j.tcs.2008.02.032","volume":"396","author":"O. Verbitsky","year":"2008","unstructured":"Verbitsky, O.: On the obfuscation complexity of planar graphs. Theor. Comput. Sci. 396(1\u20133), 294\u2013300 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"9125_CR16","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1007\/BF01594196","volume":"114","author":"K. Wagner","year":"1937","unstructured":"Wagner, K.: \u00dcber eine Eigenschaft der ebene Komplexe. Math. Ann. 114, 570\u2013590 (1937)","journal-title":"Math. Ann."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-008-9125-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-008-9125-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-008-9125-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T23:47:36Z","timestamp":1559087256000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-008-9125-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12,12]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["9125"],"URL":"https:\/\/doi.org\/10.1007\/s00454-008-9125-3","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,12,12]]}}}