{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:20:09Z","timestamp":1760440809894},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2009,12]]},"DOI":"10.1007\/s00454-008-9130-6","type":"journal-article","created":{"date-parts":[[2009,1,7]],"date-time":"2009-01-07T20:10:31Z","timestamp":1231359031000},"page":"542-569","source":"Crossref","is-referenced-by-count":17,"title":["Untangling a Planar Graph"],"prefix":"10.1007","volume":"42","author":[{"given":"Xavier","family":"Goaoc","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Kratochv\u00edl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoshio","family":"Okamoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chan-Su","family":"Shin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Spillner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Wolff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,1,9]]},"reference":[{"key":"9130_CR1","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1007\/BF01944353","volume":"16","author":"D. Avis","year":"1996","unstructured":"Avis, D.: Generating rooted triangulations without repetitions. Algorithmica 16, 618\u2013632 (1996)","journal-title":"Algorithmica"},{"key":"9130_CR2","unstructured":"Bose, P., Dujmovi\u0107, V., Hurtado, F., Langerman, S., Morin, P., Wood, D.R.: A polynomial bound for untangling geometric planar graphs. In: P. Ossona de Mendez, D. Poulalhon, M. Pocchiola, J.L. Ram\u00edrez Alfons\u00edn, G. Schaeffer (eds.) Proc. Internat. Conf. Topological Geom. Graph Theory (TGGT\u201908). Electr. Notes Discrete Math., pp. 205\u2013210 (2008). Long version available at http:\/\/arxiv.org\/abs\/0710.1641"},{"key":"9130_CR3","doi-asserted-by":"crossref","unstructured":"Canny, J.: Some algebraic and geometric computations in PSPACE. In: Proc. of the 20th ACM Sympos. Theory Comput. (STOC\u201988), pp. 460\u2013469 (1988)","DOI":"10.1145\/62212.62257"},{"key":"9130_CR4","unstructured":"Cibulka, J.: Untangling polygons and graphs. In: P. Ossona de Mendez, D. Poulalhon, M. Pocchiola, J.L. Ram\u00edrez Alfons\u00edn, G. Schaeffer (eds.) Proc. of Internat. Conf. Topological Geom. Graph Theory (TGGT\u201908), Electr. Notes Discrete Math. pp. 200\u2013204 (2008). Long version available at http:\/\/arxiv.org\/abs\/0802.1312"},{"key":"9130_CR5","first-page":"463","volume":"2","author":"P. Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463\u2013470 (1935)","journal-title":"Compos. Math."},{"key":"9130_CR6","first-page":"229","volume":"11","author":"I. F\u00e1ry","year":"1948","unstructured":"F\u00e1ry, I.: On straight-line representation of planar graphs. Acta Sci. Math. (Szeged) 11, 229\u2013233 (1948)","journal-title":"Acta Sci. Math. (Szeged)"},{"key":"9130_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. of the 15th International Symposium on Graph Drawing (GD\u201907)","author":"X. Goaoc","year":"2008","unstructured":"Goaoc, X., Kratochv\u00edl, J., Okamoto, Y., Shin, Ch.-S., Wolff, A.: Moving vertices to make drawings plane. In: Proc. of the 15th International Symposium on Graph Drawing (GD\u201907). Lecture Notes in Computer Science, vol. 4875, pp. 101\u2013112. Springer, Berlin (2008)"},{"key":"9130_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 drawing of graphs with non-convex boundary. Discrete Appl. Math. 156, 2368\u20132380 (2008)","journal-title":"Discrete Appl. Math."},{"key":"9130_CR9","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.E.: Efficient planarity testing. J. ACM 21, 549\u2013568 (1974)","journal-title":"J. ACM"},{"key":"9130_CR10","unstructured":"Kang, M., Pikhurko, O., Ravsky, A., Schacht, M., Verbitsky, O.: Obfuscated drawings of planar graphs. ArXiv report (March 2008). Available at http:\/\/arxiv.org\/abs\/0803.0858"},{"issue":"1","key":"9130_CR11","doi-asserted-by":"crossref","first-page":"115","DOI":"10.7155\/jgaa.00046","volume":"6","author":"M. Kaufmann","year":"2002","unstructured":"Kaufmann, M., Wiese, R.: Embedding vertices at points: Few bends suffice for planar graphs. J. Graph Algorithms Appl. 6(1), 115\u2013129 (2002)","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"9130_CR12","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1137\/0405033","volume":"5","author":"D.E. Knuth","year":"1992","unstructured":"Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM J. Discrete Math. 5(3), 422\u2013427 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"9130_CR13","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1006\/jctb.1994.1071","volume":"62","author":"J. Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J., Matou\u0161ek, J.: Intersection graphs of segments. J. Combin. Theory Ser. B 62, 289\u2013315 (1994)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"9130_CR14","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"key":"9130_CR15","unstructured":"Liske, N.: Planarity game. http:\/\/www.creativecouple.de\/en\/Projects\/Planarity.html (accessed 8 September 2008)"},{"key":"9130_CR16","doi-asserted-by":"crossref","unstructured":"Lubiw, A., Petrick, M., Spriggs, M.: Morphing orthogonal planar graph drawings. In: Proc. of the 17th Annu. ACM-SIAM Symposium on Discrete Algorithms (SODA\u201906), pp. 222\u2013230 (2006)","DOI":"10.1145\/1109557.1109583"},{"issue":"2","key":"9130_CR17","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1006\/jvlc.1995.1010","volume":"6","author":"K. Misue","year":"1995","unstructured":"Misue, K., Eades, P., Lai, W., Sugiyama, K.: Layout adjustment and the mental map. J. Visual Lang. Comput. 6(2), 183\u2013210 (1995)","journal-title":"J. Visual Lang. Comput."},{"issue":"4","key":"9130_CR18","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."},{"issue":"4","key":"9130_CR19","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1007\/PL00007258","volume":"17","author":"J. Pach","year":"2001","unstructured":"Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graphs Comb. 17(4), 717\u2013728 (2001)","journal-title":"Graphs Comb."},{"key":"9130_CR20","unstructured":"Ravsky, A., Verbitsky, O.: On collinear sets in straight line drawings. ArXiv report (June\u2013July 2008). Available at http:\/\/arxiv.org\/abs\/0806.0253"},{"issue":"3","key":"9130_CR21","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J. Renegar","year":"1992","unstructured":"Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals, part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals. J. Symb. Comput. 13(3), 255\u2013300 (1992)","journal-title":"J. Symb. Comput."},{"key":"9130_CR22","doi-asserted-by":"crossref","first-page":"179","DOI":"10.4153\/CJM-1961-015-3","volume":"13","author":"C. Schensted","year":"1961","unstructured":"Schensted, C.: Longest increasing and decreasing subsequences. Can. J. Math. 13, 179\u2013191 (1961)","journal-title":"Can. J. Math."},{"issue":"4","key":"9130_CR23","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/BF00353652","volume":"5","author":"W. Schnyder","year":"1989","unstructured":"Schnyder, W.: Planar graphs and poset dimension. Order 5(4), 323\u2013343 (1989)","journal-title":"Order"},{"key":"9130_CR24","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. of the 34th International Conference 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. of the 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM\u201908). Lecture Notes in Computer Science, vol. 4910, pp. 473\u2013484. Springer, Berlin (2008)"},{"key":"9130_CR25","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1090\/S0002-9939-1951-0041425-5","volume":"2","author":"S.K. Stein","year":"1951","unstructured":"Stein, S.K.: Convex maps. Proc. Am. Math. Soc. 2, 464\u2013466 (1951)","journal-title":"Proc. Am. Math. Soc."},{"key":"9130_CR26","unstructured":"Tantalo, J.: Planarity. Web site at http:\/\/planarity.net\/ (accessed 21 May 2007)"},{"issue":"1\u20133","key":"9130_CR27","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) (first published at http:\/\/arxiv.org\/abs\/0705.3748 )","journal-title":"Theor. Comput. Sci."},{"key":"9130_CR28","first-page":"26","volume":"46","author":"K. Wagner","year":"1936","unstructured":"Wagner, K.: Bemerkungen zum Vierfarbenproblem. Jahresbericht Deutsch. Math. Verein. 46, 26\u201332 (1936)","journal-title":"Jahresbericht Deutsch. Math. Verein."},{"key":"9130_CR29","unstructured":"Watanabe, M.: Open problem. In: 5th Czech\u2013Slovak Symposium on Combinatorics (1998)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-008-9130-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T22:59:05Z","timestamp":1558047545000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-008-9130-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,9]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["9130"],"URL":"https:\/\/doi.org\/10.1007\/s00454-008-9130-6","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,9]]}}}