{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:13:37Z","timestamp":1778498017257,"version":"3.51.4"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031555978","type":"print"},{"value":"9783031555985","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-55598-5_22","type":"book-chapter","created":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T18:01:53Z","timestamp":1709661713000},"page":"336-349","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Geometric Thickness of\u00a0Multigraphs is $$\\exists \\mathbb {R}$$-Complete"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1441-4189","authenticated-orcid":false,"given":"Henry","family":"F\u00f6rster","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5764-7719","authenticated-orcid":false,"given":"Philipp","family":"Kindermann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4563-2864","authenticated-orcid":false,"given":"Tilmann","family":"Miltzow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3147-0083","authenticated-orcid":false,"given":"Irene","family":"Parada","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5161-3841","authenticated-orcid":false,"given":"Soeren","family":"Terziadis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7166-4467","authenticated-orcid":false,"given":"Birgit","family":"Vogtenhuber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,6]]},"reference":[{"issue":"2","key":"22_CR1","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1070\/SM1976v030n02ABEH002267","volume":"30","author":"VB Alekseev","year":"1976","unstructured":"Alekseev, V.B., Gon\u010dakov, V.S.: The thickness of an arbitrary complete graph. Math. USSR-Sbornik 30(2), 187 (1976)","journal-title":"Math. USSR-Sbornik"},{"key":"22_CR2","doi-asserted-by":"publisher","first-page":"850","DOI":"10.4153\/CJM-1965-084-2","volume":"17","author":"LW Beineke","year":"1965","unstructured":"Beineke, L.W., Harary, F.: The thickness of the complete graph. Canadian J. Math. 17, 850\u2013859 (1965)","journal-title":"Canadian J. Math."},{"key":"22_CR3","unstructured":"Brandenburg, F.J.: Straight-line drawings of 1-planar graphs. arXiv preprint arXiv:2109.01692 (2021)"},{"issue":"1","key":"22_CR4","doi-asserted-by":"publisher","first-page":"259","DOI":"10.7155\/jgaa.00356","volume":"19","author":"J Cardinal","year":"2015","unstructured":"Cardinal, J., Kusters, V.: The complexity of simultaneous geometric graph embedding. J. Graph Algor. Appl. 19(1), 259\u2013272 (2015)","journal-title":"J. Graph Algor. Appl."},{"issue":"3","key":"22_CR5","doi-asserted-by":"publisher","first-page":"5","DOI":"10.7155\/jgaa.00023","volume":"4","author":"MB Dillencourt","year":"2000","unstructured":"Dillencourt, M.B., Eppstein, D., Hirschberg, D.S.: Geometric thickness of complete graphs. J. Graph Algor. Appl. 4(3), 5\u201317 (2000)","journal-title":"J. Graph Algor. Appl."},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"Dujmovic, V., Joret, G., Micek, P., Morin, P., Ueckerdt, T., Wood, D.R.: Planar graphs have bounded queue-number. J. ACM 67(4), 22:1\u201322:38 (2020)","DOI":"10.1145\/3385731"},{"key":"22_CR7","unstructured":"Dujmovic, V., Morin, P.: Personal communication (2022)"},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Dujmovic, V., Morin, P., Wood, D.R.: Graph product structure for non-minor-closed classes. J. Comb. Theory, Ser. B 162, 34\u201367 (2023)","DOI":"10.1016\/j.jctb.2023.03.004"},{"issue":"2","key":"22_CR9","first-page":"497","volume":"6","author":"V Dujmovic","year":"2004","unstructured":"Dujmovic, V., P\u00f3r, A., Wood, D.R.: Track layouts of graphs. Discret. Math. Theor. Comput. Sci. 6(2), 497\u2013522 (2004)","journal-title":"Discret. Math. Theor. Comput. Sci."},{"key":"22_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.comgeo.2016.03.003","volume":"56","author":"S Durocher","year":"2016","unstructured":"Durocher, S., Gethner, E., Mondal, D.: Thickness and colorability of geometric graphs. Comput. Geom. 56, 1\u201318 (2016)","journal-title":"Comput. Geom."},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"Eppstein, D.: Separating thickness from geometric thickness. In: Towards a Theory of Geometric Graphs, Contemporary Mathematics, vol. 342, pp. 75\u201386. American Mathematical Society (2004)","DOI":"10.1090\/conm\/342\/06132"},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"Erickson, J., van der Hoog, I., Miltzow, T.: Smoothing the gap between NP and ER. In: Proceedings 61st IEEE Symposium on Foundations of Computer Science (FOCS), pp. 1022\u20131033. ACM (2020)","DOI":"10.1109\/FOCS46700.2020.00099"},{"key":"22_CR13","doi-asserted-by":"publisher","unstructured":"Estrella-Balderrama, A., Gassner, E., J\u00fcnger, M., Percan, M., Schaefer, M., Schulz, M.: Simultaneous geometric graph embeddings. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) Graph Drawing. LNCS, vol. 4875, pp. 280\u2013290. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-77537-9_28","DOI":"10.1007\/978-3-540-77537-9_28"},{"key":"22_CR14","unstructured":"Fekete, S., Keldenich, P., Krupke, D., Schirra, S.: CG:SHOP 2022. https:\/\/cgshop.ibr.cs.tu-bs.de\/competition\/cg-shop-2022"},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"F\u00f6rster, H., Kindermann, P., Miltzow, T., Parada, I., Terziadis, S., Vogtenhuber, B.: Geometric thickness of multigraphs is $$\\exists $$R-complete. arXiv preprint arXiv:2312.05010 (2023)","DOI":"10.1007\/978-3-031-55598-5_22"},{"key":"22_CR16","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1090\/S0002-9904-1961-10677-0","volume":"67","author":"F Harary","year":"1961","unstructured":"Harary, F.: Research problem. Bull. Am. Math. Soc. 67, 542 (1961)","journal-title":"Bull. Am. Math. Soc."},{"key":"22_CR17","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF02992822","volume":"39","author":"PC Kainen","year":"1973","unstructured":"Kainen, P.C.: Thickness and coarseness of graphs. Abh. Math. Semin. Univ. Hambg. 39, 88\u201395 (1973)","journal-title":"Abh. Math. Semin. Univ. Hambg."},{"issue":"1","key":"22_CR18","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1017\/S030500410006028X","volume":"93","author":"A Mansfield","year":"1983","unstructured":"Mansfield, A.: Determining the thickness of graphs is NP-hard. Math. Proc. Camb. Philos. Soc. 93(1), 9\u201323 (1983)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"22_CR19","unstructured":"Nishizeki, T., Chiba, N.: Planar Graphs: Theory and Algorithms. Elsevier (1988)"},{"key":"22_CR20","volume-title":"F\u00e4rbungsprobleme auf Fl\u00e4chen und Graphen, Mathematische Monographien [Mathematical Monographs]","author":"G Ringel","year":"1959","unstructured":"Ringel, G.: F\u00e4rbungsprobleme auf Fl\u00e4chen und Graphen, Mathematische Monographien [Mathematical Monographs], vol. 2. VEB Deutscher Verlag der Wissenschaften, Berlin (1959)"},{"key":"22_CR21","doi-asserted-by":"publisher","unstructured":"Schaefer, M.: Complexity of some geometric and topological problems. In: Eppstein, D., Gansner, E.R. (eds.) Graph Drawing. LNCS, vol. 5849, pp. 334\u2013344. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11805-0_32","DOI":"10.1007\/978-3-642-11805-0_32"},{"issue":"1","key":"22_CR22","doi-asserted-by":"publisher","first-page":"29","DOI":"10.7155\/jgaa.00548","volume":"25","author":"M Schaefer","year":"2021","unstructured":"Schaefer, M.: Complexity of geometric $$k$$-planarity for fixed $$k$$. J. Graph Algor. Appl. 25(1), 29\u201341 (2021)","journal-title":"J. Graph Algor. Appl."},{"issue":"1","key":"22_CR23","doi-asserted-by":"publisher","first-page":"195","DOI":"10.7155\/jgaa.00557","volume":"25","author":"M Schaefer","year":"2021","unstructured":"Schaefer, M.: On the complexity of some geometric problems with fixed parameters. J. Graph Algor. Appl. 25(1), 195\u2013218 (2021)","journal-title":"J. Graph Algor. Appl."},{"key":"22_CR24","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/S1385-7258(63)50055-9","volume":"66","author":"WT Tutte","year":"1963","unstructured":"Tutte, W.T.: The thickness of a graph. Indagat. Math. (Proc.) 66, 567\u2013577 (1963)","journal-title":"Indagat. Math. (Proc.)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2024: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-55598-5_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,13]],"date-time":"2024-11-13T21:30:48Z","timestamp":1731533448000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-55598-5_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031555978","9783031555985"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-55598-5_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"6 March 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Puerto Varas","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chile","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 March 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 March 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/latin2024.cmm.uchile.cl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"92","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"44","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"48% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}