{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T14:11:18Z","timestamp":1760710278378,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,6,12]],"date-time":"2020-06-12T00:00:00Z","timestamp":1591920000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,12]],"date-time":"2020-06-12T00:00:00Z","timestamp":1591920000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["M2281-N35"],"award-info":[{"award-number":["M2281-N35"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2020,8]]},"DOI":"10.1007\/s10878-020-00586-0","type":"journal-article","created":{"date-parts":[[2020,6,12]],"date-time":"2020-06-12T15:03:42Z","timestamp":1591974222000},"page":"279-302","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Crossing minimization in perturbed drawings"],"prefix":"10.1007","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8485-1774","authenticated-orcid":false,"given":"Radoslav","family":"Fulek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,12]]},"reference":[{"issue":"4","key":"586_CR1","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1007\/s00454-017-9918-3","volume":"58","author":"HA Akitaya","year":"2017","unstructured":"Akitaya HA, Aloupis G, Erickson J, T\u00f3th CD (2017) Recognizing weakly simple polygons. Discrete Comput Geom 58(4):785\u2013821. https:\/\/doi.org\/10.1007\/s00454-017-9918-3","journal-title":"Discrete Comput Geom"},{"doi-asserted-by":"publisher","unstructured":"Akitaya HA, Fulek R, T\u00f3th CD (2018) Recognizing weak embeddings of graphs. In Proceedings 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 274\u2013292. SIAM. https:\/\/doi.org\/10.1137\/1.9781611975031.20","key":"586_CR2","DOI":"10.1137\/1.9781611975031.20"},{"issue":"6","key":"586_CR3","doi-asserted-by":"publisher","first-page":"2484","DOI":"10.1007\/s00453-018-00541-w","volume":"81","author":"P Angelini","year":"2019","unstructured":"Angelini P, Da Lozzo G (2019) Clustered planarity with pipes. Algorithmica 81(6):2484\u20132526. https:\/\/doi.org\/10.1007\/s00453-018-00541-w","journal-title":"Algorithmica"},{"issue":"4","key":"586_CR4","doi-asserted-by":"publisher","first-page":"1022","DOI":"10.1007\/s00453-016-0128-9","volume":"77","author":"P Angelini","year":"2017","unstructured":"Angelini P, Da Lozzo G, Di Battista G, Frati F (2017) Strip planarity testing for embedded planar graphs. Algorithmica 77(4):1022\u20131059. https:\/\/doi.org\/10.1007\/s00453-016-0128-9","journal-title":"Algorithmica"},{"issue":"2","key":"586_CR5","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/s00454-012-9440-6","volume":"49","author":"S Cabello","year":"2013","unstructured":"Cabello S (2013) Hardness of approximation for crossing number. Discrete Comput Geom 49(2):348\u2013358. https:\/\/doi.org\/10.1007\/s00454-012-9440-6","journal-title":"Discrete Comput Geom"},{"issue":"5","key":"586_CR6","doi-asserted-by":"publisher","first-page":"1803","DOI":"10.1137\/120872310","volume":"42","author":"S Cabello","year":"2013","unstructured":"Cabello S, Mohar B (2013) Adding one edge to planar graphs makes crossing number and 1-planarity hard. SIAM J Comput 42(5):1803\u20131829. https:\/\/doi.org\/10.1137\/120872310","journal-title":"SIAM J Comput"},{"doi-asserted-by":"publisher","unstructured":"Chang HC, Erickson J, Xu C (2015) Detecting weakly simple polygons. In Proceedings 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1655\u20131670, https:\/\/doi.org\/10.1137\/1.9781611973730.110","key":"586_CR7","DOI":"10.1137\/1.9781611973730.110"},{"doi-asserted-by":"publisher","unstructured":"Chuzhoy J (2011) An algorithm for the graph crossing number problem. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pages 303\u2013312. ACM, Preprint, arXiv:1012.0255 isbn = 978-1-4503-0691-1. https:\/\/doi.org\/10.1145\/1993636.1993678","key":"586_CR8","DOI":"10.1145\/1993636.1993678"},{"issue":"3","key":"586_CR9","doi-asserted-by":"publisher","first-page":"391","DOI":"10.7155\/jgaa.00115","volume":"9","author":"PF Cortese","year":"2005","unstructured":"Cortese PF, Di Battista G, Patrignani M, Pizzonia M (2005) Clustering cycles into cycles of clusters. J Graph Alg Appl 9(3):391\u2013413. https:\/\/doi.org\/10.7155\/jgaa.00115","journal-title":"J Graph Alg Appl"},{"issue":"7","key":"586_CR10","doi-asserted-by":"publisher","first-page":"1856","DOI":"10.1016\/j.disc.2007.12.090","volume":"309","author":"PF Cortese","year":"2009","unstructured":"Cortese PF, Di Battista G, Patrignani M, Pizzonia M (2009) On embedding a cycle in a plane graph. Discrete Math 309(7):1856\u20131869. https:\/\/doi.org\/10.1016\/j.disc.2007.12.090","journal-title":"Discrete Math"},{"issue":"1","key":"586_CR11","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1137\/S0097539700373520","volume":"32","author":"G Even","year":"2002","unstructured":"Even G, Guha S, Schieber B (2002) Improved approximations of crossings in graph drawings and VLSI layout areas. SIAM J Comput 32(1):231\u2013252. https:\/\/doi.org\/10.1137\/S0097539700373520","journal-title":"SIAM J Comput"},{"doi-asserted-by":"publisher","unstructured":"Feng QW, Cohen RF, Eades P (1995a) How to draw a planar clustered graph. In: Du DZ, Li M (ed). Proceedings 1st Conference on Computing and combinatorics (COCOON), vol 959 of LNCS, pp 21\u201330. Springer, Berlin. https:\/\/doi.org\/10.1007\/BFb0030816","key":"586_CR12","DOI":"10.1007\/BFb0030816"},{"doi-asserted-by":"publisher","unstructured":"Feng QW, Cohen RF, Eades P (1995b) Planarity for clustered graphs. In: Paul S (ed) Proceedings 3rd European Symposium on Algorithms (ESA), vol 979 of LNCS, pp 213\u2013226, Springer, Berlin https:\/\/doi.org\/10.1007\/3-540-60313-1_145","key":"586_CR13","DOI":"10.1007\/3-540-60313-1_145"},{"doi-asserted-by":"publisher","unstructured":"Fulek R, Kyn\u010dl J (2018) Hanani\u2013Tutte for approximating maps of graphs. In Proceedings 34th Symposium on Computational Geometry (SoCG), vol 99 of LIPIcs, pp 39:1\u201339:15, Dagstuhl, Germany. https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2018.39","key":"586_CR14","DOI":"10.4230\/LIPIcs.SoCG.2018.39"},{"issue":"3","key":"586_CR15","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"MR Garey","year":"1982","unstructured":"Garey MR, Johnson DS (1982) Crossing number is NP-complete. SIAM J Algebr Discrete Methods 4(3):312\u2013316. https:\/\/doi.org\/10.1137\/0604033","journal-title":"SIAM J Algebr Discrete Methods"},{"issue":"2","key":"586_CR16","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/j.jcss.2003.07.008","volume":"68","author":"M Grohe","year":"2004","unstructured":"Grohe M (2004) Computing crossing numbers in quadratic time. J Comput Syst Sci 68(2):285\u2013302. https:\/\/doi.org\/10.1016\/j.jcss.2003.07.008","journal-title":"J Comput Syst Sci"},{"key":"586_CR17","doi-asserted-by":"publisher","first-page":"135","DOI":"10.4064\/fm-23-1-135-142","volume":"23","author":"H Hanani","year":"1934","unstructured":"Hanani H (1934) \u00dcber wesentlich unpl\u00e4ttbare Kurven im drei-dimensionalen Raume. Fundam Math 23:135\u2013142. https:\/\/doi.org\/10.4064\/fm-23-1-135-142","journal-title":"Fundam Math"},{"issue":"1","key":"586_CR18","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/BF02772960","volume":"51","author":"J Hass","year":"1985","unstructured":"Hass J, Scott P (1985) Intersections of curves on surfaces. Isr J Math 51(1):90\u2013120. https:\/\/doi.org\/10.1007\/BF02772960","journal-title":"Isr J Math"},{"doi-asserted-by":"publisher","unstructured":"Hlinen\u00fd P, Dern\u00e1r M (2016) Crossing number is hard for kernelization. In 32nd International Symposium on Computational Geometry (SoCG), vol 51 of LIPIcs, pp 42:1\u201342:10. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2016.42","key":"586_CR19","DOI":"10.4230\/LIPIcs.SoCG.2016.42"},{"doi-asserted-by":"publisher","unstructured":"J\u00fcnger M, Leipert S, Mutzel P (1998) Level planarity testing in linear time. In: Whitesides SH (ed). Proceedings 6th Symposium on Graph Drawing (GD), vol 1547 of LNCS, pp 224\u2013237. Springer, Berlin. https:\/\/doi.org\/10.1007\/3-540-37623-2_17","key":"586_CR20","DOI":"10.1007\/3-540-37623-2_17"},{"doi-asserted-by":"publisher","unstructured":"Kawarabayashi KI, Reed BA (2007) Computing crossing number in linear time. In Proceedings 39th ACM Symposium on Theory of Computing (STOC), pp 382\u2013390. ACM. https:\/\/doi.org\/10.1145\/1250790.1250848","key":"586_CR21","DOI":"10.1145\/1250790.1250848"},{"issue":"1","key":"586_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0166-8641(97)00121-1","volume":"87","author":"D Repov\u0161","year":"1998","unstructured":"Repov\u0161 D, Skopenkov AB (1998) A deleted product criterion for approximability of maps by embeddings. Topol Appl 87(1):1\u201319. https:\/\/doi.org\/10.1016\/S0166-8641(97)00121-1","journal-title":"Topol Appl"},{"issue":"1","key":"586_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0166-8641(03)00069-5","volume":"134","author":"M Skopenkov","year":"2003","unstructured":"Skopenkov M (2003) On approximability by embeddings of cycles in the plane. Topol Appl 134(1):1\u201322. https:\/\/doi.org\/10.1016\/S0166-8641(03)00069-5","journal-title":"Topol Appl"},{"key":"586_CR24","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0021-9800(70)80007-2","volume":"8","author":"WT Tutte","year":"1970","unstructured":"Tutte WT (1970) Toward a theory of crossing numbers. J Comb Theory 8:45\u201353. https:\/\/doi.org\/10.1016\/S0021-9800(70)80007-2","journal-title":"J Comb Theory"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00586-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00586-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00586-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,11]],"date-time":"2021-06-11T23:56:47Z","timestamp":1623455807000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00586-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,12]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["586"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00586-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,6,12]]},"assertion":[{"value":"12 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}