{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:17Z","timestamp":1740109577246,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T00:00:00Z","timestamp":1579219200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T00:00:00Z","timestamp":1579219200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s00454-019-00167-x","type":"journal-article","created":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T15:02:46Z","timestamp":1579273366000},"page":"999-1027","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Every Collinear Set in a Planar Graph is Free"],"prefix":"10.1007","volume":"65","author":[{"given":"Vida","family":"Dujmovi\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrizio","family":"Frati","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Gon\u00e7alves","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0471-4118","authenticated-orcid":false,"given":"Pat","family":"Morin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G\u00fcnter","family":"Rote","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,17]]},"reference":[{"key":"167_CR1","doi-asserted-by":"crossref","unstructured":"Angelini, P., Binucci, C., Evans, W., Hurtado, F., Liotta, G., Mchedlidze, T., Meijer, H., Okamoto, Y.: Universal point subsets for planar graphs. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) 23rd International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 7676, pp. 423\u2013432. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-35261-4_45"},{"issue":"2","key":"167_CR2","doi-asserted-by":"publisher","first-page":"177","DOI":"10.7155\/jgaa.00318","volume":"18","author":"MJ Bannister","year":"2014","unstructured":"Bannister, M.J., Cheng, Z., Devanny, W.E., Eppstein, D.: Superpatterns and universal point sets. J. Graph Algorithms Appl. 18(2), 177\u2013209 (2014)","journal-title":"J. Graph Algorithms Appl."},{"issue":"6","key":"167_CR3","doi-asserted-by":"publisher","first-page":"983","DOI":"10.7155\/jgaa.00446","volume":"21","author":"L Barba","year":"2017","unstructured":"Barba, L., Evans, W., Hoffmann, M., Kusters, V., Saumell, M., Speckmann, B.: Column planarity and partially-simultaneous geometric embedding. J. Graph Algorithms Appl. 21(6), 983\u20131002 (2017)","journal-title":"J. Graph Algorithms Appl."},{"issue":"3","key":"167_CR4","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0925-7721(01)00069-4","volume":"23","author":"P Bose","year":"2002","unstructured":"Bose, P.: On embedding an outer-planar graph in a point set. Comput. Geom. 23(3), 303\u2013312 (2002)","journal-title":"Comput. Geom."},{"issue":"4","key":"167_CR5","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1007\/s00454-008-9125-3","volume":"42","author":"P Bose","year":"2009","unstructured":"Bose, P., Dujmovi\u0107, V., Hurtado, F., Langerman, S., Morin, P., Wood, D.R.: A polynomial bound for untangling geometric planar graphs. Discrete Comput. Geom. 42(4), 570\u2013585 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"167_CR6","unstructured":"Cano, J., T\u00f3th, Cs.D., Urrutia, J.: Upper bound constructions for untangling planar geometric graphs. SIAM J. Discrete Math. 28(4), 1935\u20131943 (2014)"},{"key":"167_CR7","doi-asserted-by":"crossref","unstructured":"Casta\u00f1eda, N., Urrutia, J.: Straight line embeddings of planar graphs on point sets. In: Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG\u201996), pp. 312\u2013318. Carleton University Press (1996)","DOI":"10.1515\/9780773591134-055"},{"issue":"2","key":"167_CR8","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/s00454-009-9150-x","volume":"43","author":"J Cibulka","year":"2010","unstructured":"Cibulka, J.: Untangling polygons and graphs. Discrete Comput. Geom. 43(2), 402\u2013411 (2010)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"167_CR9","first-page":"94","volume":"9","author":"G Da Lozzo","year":"2018","unstructured":"Da Lozzo, G., Dujmovi\u0107, V., Frati, F., Mchedlidze, T., Roselli, V.: Drawing planar graphs with many collinear vertices. J. Comput. Geom. 9(1), 94\u2013130 (2018)","journal-title":"J. Comput. Geom."},{"issue":"1","key":"167_CR10","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H de Fraysseix","year":"1990","unstructured":"de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41\u201351 (1990)","journal-title":"Combinatorica"},{"issue":"3\u20134","key":"167_CR11","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/S0925-7721(98)00039-X","volume":"11","author":"O Devillers","year":"1998","unstructured":"Devillers, O., Liotta, G., Preparata, F.P., Tamassia, R.: Checking the convexity of polytopes and the planarity of subdivisions. Comput. Geom. 11(3\u20134), 187\u2013208 (1998)","journal-title":"Comput. Geom."},{"issue":"11","key":"167_CR12","doi-asserted-by":"publisher","first-page":"3126","DOI":"10.1093\/comjnl\/bxv048","volume":"58","author":"E Di Giacomo","year":"2015","unstructured":"Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H., Wismath, S.K.: Planar and quasi-planar simultaneous geometric embedding. Comput. J. 58(11), 3126\u20133140 (2015)","journal-title":"Comput. J."},{"issue":"1","key":"167_CR13","doi-asserted-by":"publisher","first-page":"121","DOI":"10.7155\/jgaa.00407","volume":"21","author":"V Dujmovi\u0107","year":"2017","unstructured":"Dujmovi\u0107, V.: The utility of untangling. J. Graph Algorithms Appl. 21(1), 121\u2013134 (2017)","journal-title":"J. Graph Algorithms Appl."},{"key":"167_CR14","first-page":"229","volume":"11","author":"I F\u00e1ry","year":"1948","unstructured":"F\u00e1ry, I.: On straight line representions of planar graphs. Acta Sci. Math. (Szeged) 11, 229\u2013233 (1948)","journal-title":"Acta Sci. Math. (Szeged)"},{"key":"167_CR15","unstructured":"Felsner, S., Rote, G.: On primal-dual circle representations. In: Fineman, J.T., Mitzenmacher, M. (eds.) In: Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA 2019). OpenAccess Series in Informatics (OASIcs), vol. 69, pp. 8:1\u20138:18. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Wadern (2019)"},{"issue":"4","key":"167_CR16","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1007\/s00454-008-9130-6","volume":"42","author":"X Goaoc","year":"2009","unstructured":"Goaoc, X., Kratochv\u00edl, J., Okamoto, Y., Shin, C.-S., Spillner, A., Wolff, A.: Untangling a planar graph. Discrete Comput. Geom. 42(4), 542\u2013569 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"167_CR17","doi-asserted-by":"publisher","first-page":"165","DOI":"10.2307\/2323956","volume":"98","author":"P Gritzmann","year":"1991","unstructured":"Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified points (solution to problem e3341). Am. Math. Monthly 98, 165\u2013166 (1991)","journal-title":"Am. Math. Monthly"},{"issue":"8","key":"167_CR18","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/j.dam.2011.01.011","volume":"159","author":"M Kang","year":"2011","unstructured":"Kang, M., Pikhurko, O., Ravsky, A., Schacht, M., Verbitsky, O.: Untangling planar graphs from a specified vertex position\u2013hard cases. Discrete Appl. Math. 159(8), 789\u2013799 (2011)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"167_CR19","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.ipl.2004.06.009","volume":"92","author":"M Kurowski","year":"2004","unstructured":"Kurowski, M.: A 1.235 lower bound on the number of points needed to draw all $$n$$-vertex planar graphs. Inf. Process. Lett. 92(2), 95\u201398 (2004)","journal-title":"Inf. Process. Lett."},{"key":"167_CR20","doi-asserted-by":"crossref","unstructured":"Mchedlidze, T., Radermacher, M., Rutter, I.: Aligned drawings of planar graphs. In: Frati, F., Ma, K.-L. (eds.) 25th International Symposium on Graph Drawing and Network Visualization (GD 2017). Lecture Notes in Computer Science, vol. 10692, pp. 3\u201316. Springer, Cham (2018)","DOI":"10.1007\/978-3-319-73915-1_1"},{"issue":"2","key":"167_CR21","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0012-365X(81)90239-9","volume":"36","author":"PJ Owens","year":"1981","unstructured":"Owens, P.J.: Non-Hamiltonian simple $$3$$-polytopes whose faces are all $$5$$-gons or $$7$$-gons. Discrete Math. 36(2), 227\u2013230 (1981)","journal-title":"Discrete Math."},{"issue":"4","key":"167_CR22","doi-asserted-by":"publisher","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":"167_CR23","unstructured":"Ravsky, A., Verbitsky, O.: On collinear sets in straight-line drawings. In: Kolman, P., Kratochv\u00edl, J. (eds.) 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011). Lecture Notes in Computer Science, vol. 6986, pp. 295\u2013306. Springer, Heidelberg (2011). arXiv:0806.0253"},{"key":"167_CR24","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1112\/plms\/s3-13.1.743","volume":"13","author":"WT Tutte","year":"1963","unstructured":"Tutte, W.T.: How to draw a graph. Proc. Lond. Math. Soc. 13, 743\u2013768 (1963)","journal-title":"Proc. Lond. Math. Soc."},{"key":"167_CR25","unstructured":"Wood, D.R.: A simple proof of the F\u00e1ry\u2013Wagner theorem (2005). CoRR, arXiv:cs\/0505047"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00167-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-019-00167-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00167-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,25]],"date-time":"2023-09-25T08:14:36Z","timestamp":1695629676000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-019-00167-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,17]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["167"],"URL":"https:\/\/doi.org\/10.1007\/s00454-019-00167-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2020,1,17]]},"assertion":[{"value":"8 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 December 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 December 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}