{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T16:15:10Z","timestamp":1770048910419,"version":"3.49.0"},"reference-count":101,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T00:00:00Z","timestamp":1762732800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T00:00:00Z","timestamp":1762732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005713","name":"Technische Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005713","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We say that a (multi)graph\n                    <jats:inline-formula>\n                      <jats:tex-math>$$ \\user2{G} = (\\user2{V},\\user2{E}) $$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    has geometric thickness\n                    <jats:italic>t<\/jats:italic>\n                    if there exists a straight-line drawing\n                    <jats:inline-formula>\n                      <jats:tex-math>$$ \\user2{\\varphi }:\\user2{V} \\to \\mathbb{R}^{{\\mathbf{2}}} $$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    and a\n                    <jats:italic>t<\/jats:italic>\n                    -coloring of its edges where no two edges sharing a point in their relative interior have the same color. The\n                    <jats:sc>Geometric Thickness<\/jats:sc>\n                    problem asks whether a given multigraph has geometric thickness at most\n                    <jats:italic>t<\/jats:italic>\n                    . This problem was shown to be NP-hard for\n                    <jats:inline-formula>\n                      <jats:tex-math>$$ \\user2{t} = \\mathbf{2} $$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    (Durocher et al. Comput Geom 56:1\u201318, 2016.\n                    <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"10.1016\/j.comgeo.2016.03.003\" ext-link-type=\"doi\">https:\/\/doi.org\/10.1016\/j.comgeo.2016.03.003<\/jats:ext-link>\n                    ). In this paper, we settle the computational complexity of\n                    <jats:sc>Geometric Thickness<\/jats:sc>\n                    by showing that it is\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\exists \\mathbb {R}$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -complete already for thickness\n                    <jats:bold>30<\/jats:bold>\n                    . Moreover, our reduction shows that the problem is\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\exists \\mathbb {R}$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -complete for\n                    <jats:bold>4392<\/jats:bold>\n                    -planar graphs, where a graph is\n                    <jats:bold>\n                      <jats:italic>k<\/jats:italic>\n                    <\/jats:bold>\n                    -planar if it admits a topological drawing with at most\n                    <jats:bold>\n                      <jats:italic>k<\/jats:italic>\n                    <\/jats:bold>\n                    crossings per edge. In the course of our paper we answer previous questions on geometric thickness and on other related problems, in particular that simultaneous graph embeddings of\n                    <jats:bold>31<\/jats:bold>\n                    edge-disjoint graphs and pseudo-segment stretchability with chromatic number\u00a0\n                    <jats:bold>30<\/jats:bold>\n                    are\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\exists \\mathbb {R}$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -complete.\n                  <\/jats:p>","DOI":"10.1007\/s00453-025-01351-7","type":"journal-article","created":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T07:23:25Z","timestamp":1762759405000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Geometric Thickness of Multigraphs is $$\\exists \\mathbb {R}$$-Complete"],"prefix":"10.1007","volume":"88","author":[{"given":"Henry","family":"F\u00f6rster","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philipp","family":"Kindermann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tillmann","family":"Miltzow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Irene","family":"Parada","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Soeren","family":"Terziadis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Birgit","family":"Vogtenhuber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,11,10]]},"reference":[{"issue":"1","key":"1351_CR1","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 Algorithms Appl. 25(1), 195\u2013218 (2021). https:\/\/doi.org\/10.7155\/jgaa.00557","journal-title":"J. Graph Algorithms Appl."},{"key":"1351_CR2","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. Indagationes Mathematicae (Proceedings) 66, 567\u2013577 (1963). https:\/\/doi.org\/10.1016\/S1385-7258(63)50055-9","journal-title":"Indagationes Mathematicae (Proceedings)"},{"key":"1351_CR3","unstructured":"Ringel, G.: F\u00e4rbungsprobleme auf Fl\u00e4chen und Graphen, Mathematische Monographien [Mathematical Monographs], vol.\u00a02, pp. viii+132. VEB Deutscher Verlag der Wissenschaften, Berlin (1959)"},{"key":"1351_CR4","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). https:\/\/doi.org\/10.1090\/S0002-9904-1961-10677-0","journal-title":"Bull. Am. Math. Soc."},{"key":"1351_CR5","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1090\/S0002-9904-1962-10850-7","volume":"68","author":"J Battle","year":"1962","unstructured":"Battle, J., Harary, F., Kodama, Y.: Every planar graph with nine vertices has a nonplanar complement. Bull. Am. Math. Soc. 68, 569\u2013571 (1962). https:\/\/doi.org\/10.1090\/S0002-9904-1962-10850-7","journal-title":"Bull. Am. Math. Soc."},{"issue":"3","key":"1351_CR6","doi-asserted-by":"publisher","first-page":"319","DOI":"10.4153\/CMB-1963-026-x","volume":"6","author":"WT Tutte","year":"1963","unstructured":"Tutte, W.T.: The non-biplanar character of the complete 9-graph. Can. Math. Bull. 6(3), 319\u2013330 (1963)","journal-title":"Can. Math. Bull."},{"issue":"1","key":"1351_CR7","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. Cambridge Philos. Soc. 93(1), 9\u201323 (1983). https:\/\/doi.org\/10.1017\/S030500410006028X","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"key":"1351_CR8","doi-asserted-by":"publisher","unstructured":"Dillencourt, M.B., Eppstein, D., Hirschberg, D.S.: Geometric thickness of complete graphs. In: Graph Drawing, 6th International Symposium, GD\u201998, Montr\u00e9al, Canada, August 1998, Proceedings, Lecture Notes in Computer Science, In: Whitesides, S. (ed.), vol. 1547, pp. 101\u2013110. Springer, Berlin (1998). https:\/\/doi.org\/10.1007\/3-540-37623-2_8","DOI":"10.1007\/3-540-37623-2_8"},{"issue":"3","key":"1351_CR9","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 Algorithms Appl. 4(3), 5\u201317 (2000). https:\/\/doi.org\/10.7155\/jgaa.00023","journal-title":"J. Graph Algorithms Appl."},{"key":"1351_CR10","doi-asserted-by":"publisher","unstructured":"Durocher, S., Gethner, E., Mondal, D.: Thickness and colorability of geometric graphs. In: Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013, L\u00fcbeck, Germany, June 19-21, 2013, Revised Papers, Lecture Notes in Computer Science, In: Brandst\u00e4dt, A., Jansen, K., Reischuk, R. (eds.), vol. 8165, pp. 237\u2013248. Springer, Berlin (2013). https:\/\/doi.org\/10.1007\/978-3-642-45043-3_21","DOI":"10.1007\/978-3-642-45043-3_21"},{"key":"1351_CR11","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). https:\/\/doi.org\/10.1016\/j.comgeo.2016.03.003","journal-title":"Comput. Geom."},{"issue":"2","key":"1351_CR12","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). https:\/\/doi.org\/10.1070\/SM1976v030n02ABEH002267","journal-title":"Math. USSR-Sbornik"},{"key":"1351_CR13","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. Can. J. Math. 17, 850\u2013859 (1965). https:\/\/doi.org\/10.4153\/CJM-1965-084-2","journal-title":"Can. J. Math."},{"key":"1351_CR14","doi-asserted-by":"publisher","unstructured":"Eppstein, D.: Separating thickness from geometric thickness. In: Towards a theory of geometric graphs, Contemp. Math., (Amer. Math. Soc.), vol. 342, pp. 75\u201386 (2004). https:\/\/doi.org\/10.1090\/conm\/342\/06132","DOI":"10.1090\/conm\/342\/06132"},{"key":"1351_CR15","doi-asserted-by":"publisher","unstructured":"Duncan, C.A., Eppstein, D., Kobourov, S.G.: The geometric thickness of low degree graphs. In: Proc. 20th ACM Symposium on Computational Geometry (SCG), pp. 340\u2013346 (2004). https:\/\/doi.org\/10.1145\/997817.997868","DOI":"10.1145\/997817.997868"},{"key":"1351_CR16","doi-asserted-by":"publisher","DOI":"10.37236\/1029","author":"J Bar\u00e1t","year":"2006","unstructured":"Bar\u00e1t, J., Matousek, J., Wood, D.R.: Bounded-degree graphs have arbitrarily large geometric thickness. Electron. J. Comb. (2006). https:\/\/doi.org\/10.37236\/1029","journal-title":"Electron. J. Comb."},{"key":"1351_CR17","doi-asserted-by":"publisher","unstructured":"Jain, R., Ricci, M., Rollin, J., Schulz, A.: On the geometric thickness of 2-degenerate graphs. In: 39th International Symposium on Computational Geometry (SoCG), LIPIcs, 258, 44:1\u201344:15 (2023). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2023.44","DOI":"10.4230\/LIPIcs.SoCG.2023.44"},{"issue":"1","key":"1351_CR18","doi-asserted-by":"publisher","first-page":"356","DOI":"10.20382\/jocg.v9i1a12","volume":"9","author":"V Dujmovic","year":"2018","unstructured":"Dujmovic, V., Wood, D.R.: Thickness and antithickness of graphs. J. Comput. Geom. 9(1), 356\u2013386 (2018). https:\/\/doi.org\/10.20382\/jocg.v9i1a12","journal-title":"J. Comput. Geom."},{"key":"1351_CR19","doi-asserted-by":"crossref","unstructured":"Fekete, S., Keldenich, P., Krupke, D., Schirra, S.: CG:SHOP 2022 \u2013 minimum partition into plane subgraphs. https:\/\/cgshop.ibr.cs.tu-bs.de\/competition\/cg-shop-2022","DOI":"10.1145\/3604907"},{"issue":"1","key":"1351_CR20","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/PL00007219","volume":"14","author":"P Mutzel","year":"1998","unstructured":"Mutzel, P., Odenthal, T., Scharbrodt, M.: The thickness of graphs: A survey. Graphs Comb. 14(1), 59\u201373 (1998). https:\/\/doi.org\/10.1007\/PL00007219","journal-title":"Graphs Comb."},{"issue":"1","key":"1351_CR21","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 Algorithms Appl. 19(1), 259\u2013272 (2015). https:\/\/doi.org\/10.7155\/jgaa.00356","journal-title":"J. Graph Algorithms Appl."},{"key":"1351_CR22","doi-asserted-by":"publisher","unstructured":"Estrella-Balderrama, A., Gassner, E., J\u00fcnger, M., Percan, M., Schaefer, M., Schulz, M.: Simultaneous geometric graph embeddings. In: In Graph drawing, LNCS, vol. 4875, pp. 280\u2013290. Springer, Berlin (2008). https:\/\/doi.org\/10.1007\/978-3-540-77537-9_28","DOI":"10.1007\/978-3-540-77537-9_28"},{"issue":"1","key":"1351_CR23","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 Algorithms Appl. 25(1), 29\u201341 (2021). https:\/\/doi.org\/10.7155\/jgaa.00548","journal-title":"J. Graph Algorithms Appl."},{"key":"1351_CR24","doi-asserted-by":"publisher","DOI":"10.1016\/J.COMGEO.2023.102036","volume":"116","author":"FJ Brandenburg","year":"2024","unstructured":"Brandenburg, F.J.: Straight-line drawings of 1-planar graphs. Comput. Geom. 116, 102036 (2024). https:\/\/doi.org\/10.1016\/J.COMGEO.2023.102036","journal-title":"Comput. Geom."},{"key":"1351_CR25","unstructured":"Dujmovic, V., Morin, P.: Personal communication (2022)"},{"issue":"2","key":"1351_CR26","doi-asserted-by":"publisher","first-page":"497","DOI":"10.46298\/dmtcs.315","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). https:\/\/doi.org\/10.46298\/dmtcs.315","journal-title":"Discret. Math. Theor. Comput. Sci."},{"key":"1351_CR27","doi-asserted-by":"publisher","unstructured":"Dujmovic, V., Joret, G., Micek, P., Morin, P., Ueckerdt, T., Wood, D.R.: Planar Graphs have Bounded Queue-Number. In: 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, In: Zuckerman, (ed.), pp. 862\u2013875. IEEE Computer Society (2019). https:\/\/doi.org\/10.1109\/FOCS.2019.00056","DOI":"10.1109\/FOCS.2019.00056"},{"issue":"4","key":"1351_CR28","doi-asserted-by":"publisher","first-page":"22:1","DOI":"10.1145\/3385731","volume":"67","author":"V Dujmovic","year":"2020","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-22:38 (2020). https:\/\/doi.org\/10.1145\/3385731","journal-title":"J. ACM"},{"key":"1351_CR29","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.jctb.2023.03.004","volume":"162","author":"V Dujmovic","year":"2023","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). https:\/\/doi.org\/10.1016\/j.jctb.2023.03.004","journal-title":"J. Comb. Theory. Ser. B"},{"key":"1351_CR30","doi-asserted-by":"publisher","unstructured":"Erickson, J., van\u00a0der Hoog, I., Miltzow, T.: Smoothing the gap between NP and ER, in Proc. 61st IEEE Symposium on Foundations of Computer Science (FOCS) (ACM), pp. 1022\u20131033 (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00099","DOI":"10.1109\/FOCS46700.2020.00099"},{"issue":"6","key":"1351_CR31","doi-asserted-by":"publisher","first-page":"S20","DOI":"10.1137\/20M1385287","volume":"53","author":"J Erickson","year":"2024","unstructured":"Erickson, J., van der Hoog, I., Miltzow, T.: Smoothing the gap between NP and ER. SIAM J. Comput. 53(6), S20-102 (2024). https:\/\/doi.org\/10.1137\/20M1385287","journal-title":"SIAM J. Comput."},{"key":"1351_CR32","doi-asserted-by":"publisher","unstructured":"Canny, J.: Some Algebraic and Geometric Computations in PSPACE. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC \u201988), pp. 460\u2013467 (1988). https:\/\/doi.org\/10.1145\/62212.62257","DOI":"10.1145\/62212.62257"},{"issue":"1","key":"1351_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L Blum","year":"1989","unstructured":"Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Am. Math. Soc. 21(1), 1\u201346 (1989). https:\/\/doi.org\/10.1090\/S0273-0979-1989-15750-9","journal-title":"Bull. Am. Math. Soc."},{"key":"1351_CR34","doi-asserted-by":"publisher","unstructured":"Schaefer, M., Cardinal, J., Miltzow, T.:The existential theory of the reals as a complexity class: a compendium. CoRR arXiv:2407.18006, https:\/\/doi.org\/10.48550\/ARXIV.2407.18006 (2024)","DOI":"10.48550\/ARXIV.2407.18006"},{"key":"1351_CR35","doi-asserted-by":"publisher","unstructured":"Schaefer, M.: Complexity of some geometric and topological problems. In: Graph drawing, Lecture Notes in Comput. Sci., vol. 5849, pp. 334\u2013344. Springer, Berlin (2010). https:\/\/doi.org\/10.1007\/978-3-642-11805-0_32","DOI":"10.1007\/978-3-642-11805-0_32"},{"key":"1351_CR36","doi-asserted-by":"publisher","unstructured":"Mn\u00ebv, N.E.: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In Topology and Geometry\u2014Rohlin Seminar, Lecture Notes in Math., vol. 1346, pp. 527\u2013543. Springer, Berlin (1988). https:\/\/doi.org\/10.1007\/BFb0082792","DOI":"10.1007\/BFb0082792"},{"key":"1351_CR37","doi-asserted-by":"publisher","unstructured":"Shor, P.W.: Stretchability of pseudolines is NP-hard. In: Applied geometry and discrete mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol.\u00a04 (Amer. Math. Soc., Providence, RI), pp. 531\u2013554 (1991). https:\/\/doi.org\/10.1090\/dimacs\/004\/41","DOI":"10.1090\/dimacs\/004\/41"},{"key":"1351_CR38","doi-asserted-by":"publisher","unstructured":"Schaefer, M.: Realizability of graphs and linkages. In: Thirty essays on geometric graph theory, pp. 461\u2013482. Springer, New York (2013). https:\/\/doi.org\/10.1007\/978-1-4614-0110-0_24","DOI":"10.1007\/978-1-4614-0110-0_24"},{"issue":"2","key":"1351_CR39","doi-asserted-by":"publisher","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(2), 289\u2013315 (1994). https:\/\/doi.org\/10.1006\/jctb.1994.1071","journal-title":"J. Combin. Theory Ser. B"},{"key":"1351_CR40","unstructured":"Matou\u0161ek, J.: Intersection graphs of segments and $$\\exists {\\mathbb{R}}$$. CoRR arXiv:1406.2636 (2014). http:\/\/arxiv.org\/abs\/1406.2636"},{"key":"1351_CR41","doi-asserted-by":"publisher","unstructured":"McDiarmid, C., M\u00fcller, T.: The number of bits needed to represent a unit disk graph, in Graph-theoretic concepts in computer science. Lecture Notes in Comput. Sci., vol. 6410, pp. 315\u2013323. Springer, Berlin (2010). https:\/\/doi.org\/10.1007\/978-3-642-16926-7_29","DOI":"10.1007\/978-3-642-16926-7_29"},{"key":"1351_CR42","doi-asserted-by":"publisher","unstructured":"Cardinal, J., Felsner, S., Miltzow, T., Tompkins, C., Vogtenhuber, B.: Intersection Graphs of Rays and Grounded Segments. In: Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers, Lecture Notes in Computer Science, In: Bodlaender, H.L., Woeginger, G.J. (eds.), vol. 10520, pp. 153\u2013166. Springer, Berlin (2017). https:\/\/doi.org\/10.1007\/978-3-319-68705-6_12","DOI":"10.1007\/978-3-319-68705-6_12"},{"issue":"2","key":"1351_CR43","doi-asserted-by":"publisher","first-page":"273","DOI":"10.7155\/jgaa.00470","volume":"22","author":"J Cardinal","year":"2018","unstructured":"Cardinal, J., Felsner, S., Miltzow, T., Tompkins, C., Vogtenhuber, B.: Intersection graphs of rays and grounded segments. J. Graph Algorithms Appl. 22(2), 273\u2013295 (2018). https:\/\/doi.org\/10.7155\/jgaa.00470","journal-title":"J. Graph Algorithms Appl."},{"key":"1351_CR44","doi-asserted-by":"publisher","unstructured":"Dobbins, M.G., Kleist, L., Miltzow, T., Rza\u017cewski, P.: $$\\forall \\exists \\mathbb{R}$$-completeness and area-universality. In: Graph-theoretic concepts in computer science, Lecture Notes in Comput. Sci., vol. 11159, pp. 164\u2013175 Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-00256-5_14","DOI":"10.1007\/978-3-030-00256-5_14"},{"issue":"1","key":"1351_CR45","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/S00454-022-00381-0","volume":"70","author":"MG Dobbins","year":"2023","unstructured":"Dobbins, M.G., Kleist, L., Miltzow, T., Rzazewski, P.: Completeness for the complexity class $$\\forall \\exists \\mathbb{R} $$ and area-universality. Discret. Comput. Geom. 70(1), 154\u2013188 (2023). https:\/\/doi.org\/10.1007\/S00454-022-00381-0","journal-title":"Discret. Comput. Geom."},{"key":"1351_CR46","unstructured":"Erickson, J.: Optimal curve straightening is $$\\exists \\mathbb{R}$$-complete. CoRR arXiv:1908.09400 (2019)"},{"key":"1351_CR47","unstructured":"Lubiw, A., Mondal, D.: On compatible triangulations with a minimum number of steiner points. In: Proceedings of the 29th Canadian Conference on Computational Geometry, CCCG 2017, July 26-28, 2017, Carleton University, Ottawa, Ontario, Canada, In: Gudmundsson, J., Smid, M.H.M. (eds.), pp. 101\u2013106 (2017)"},{"key":"1351_CR48","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.tcs.2020.06.014","volume":"835","author":"A Lubiw","year":"2020","unstructured":"Lubiw, A., Mondal, D.: On compatible triangulations with a minimum number of Steiner points. Theoret. Comput. Sci. 835, 97\u2013107 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2020.06.014","journal-title":"Theoret. Comput. Sci."},{"key":"1351_CR49","doi-asserted-by":"publisher","unstructured":"Abrahamsen, M., Kleist, L., Miltzow, T.: Geometric embeddability of complexes is $$\\exists \\mathbb{R}$$-complete. In: 39th International Symposium on Computational Geometry, LIPIcs, vol. 258, pp. Art. No. 1, 19. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2023). https:\/\/doi.org\/10.4230\/lipics.socg.2023.1","DOI":"10.4230\/lipics.socg.2023.1"},{"issue":"1","key":"1351_CR50","doi-asserted-by":"publisher","first-page":"9:1","DOI":"10.1145\/3707201","volume":"72","author":"M Abrahamsen","year":"2025","unstructured":"Abrahamsen, M., Kleist, L., Miltzow, T.: Geometric embeddability of complexes is $$\\exists \\mathbb{R} $$-complete. J. ACM 72(1), 9:1-9:26 (2025). https:\/\/doi.org\/10.1145\/3707201","journal-title":"J. ACM"},{"issue":"2","key":"1351_CR51","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/s00454-015-9714-x","volume":"54","author":"KA Adiprasito","year":"2015","unstructured":"Adiprasito, K.A., Padrol, A., Theran, L.: Universality theorems for inscribed polytopes and Delaunay triangulations. Discrete Comput. Geom. 54(2), 412\u2013431 (2015). https:\/\/doi.org\/10.1007\/s00454-015-9714-x","journal-title":"Discrete Comput. Geom."},{"key":"1351_CR52","unstructured":"Dobbins, M.G., Holmsen, A.F., Miltzow, T.: A universality theorem for nested polytopes. CoRR arXiv:1908.02213 (2019)"},{"key":"1351_CR53","doi-asserted-by":"publisher","unstructured":"Richter-Gebert, J.: Realization spaces of polytopes. Lecture Notes in Math., vol. 1643, pp. xii+187. Springer-Verlag, Berlin (1996). https:\/\/doi.org\/10.1007\/BFb0093761","DOI":"10.1007\/BFb0093761"},{"issue":"4","key":"1351_CR54","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1090\/S0273-0979-1995-00604-X","volume":"32","author":"J Richter-Gebert","year":"1995","unstructured":"Richter-Gebert, J., Ziegler, G.M.: Realization spaces of $$4$$-polytopes are universal. Bull. Am. Math. Soc. (N.S.) 32(4), 403\u2013412 (1995). https:\/\/doi.org\/10.1090\/S0273-0979-1995-00604-X","journal-title":"Bull. Am. Math. Soc. (N.S.)"},{"key":"1351_CR55","unstructured":"Verkama, E.: Repairing the universality theorem for 4-polytopes. Master\u2019s thesis, Aalto University School of Science (2023)"},{"key":"1351_CR56","doi-asserted-by":"publisher","unstructured":"Attia, L., Oliu-Barton, M.: Stationary equilibria in discounted stochastic games. Dynamic Games and Applications pp. 1\u201314 (2023). https:\/\/doi.org\/10.1007\/s13235-023-00495-x","DOI":"10.1007\/s13235-023-00495-x"},{"key":"1351_CR57","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-031-43254-5_3","volume-title":"Algorithmic Game Theory","author":"V Bil\u00f2","year":"2023","unstructured":"Bil\u00f2, V., Hansen, K.A., Mavronicolas, M.: Computational Complexity of Decision Problems About Nash Equilibria in Win-Lose Multi-player Games. In: Deligkas, A., Filos-Ratsikas, A. (eds.) Algorithmic Game Theory, pp. 40\u201357. Springer Nature Switzerland, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-43254-5_3"},{"key":"1351_CR58","doi-asserted-by":"publisher","unstructured":"Brenguier, R.: Robust equilibria in mean-payoff games, in Foundations of software science and computation structures. In: Lecture Notes in Comput. Sci, vol. 9634, pp. 217\u2013233. Springer, Berlin (2016). https:\/\/doi.org\/10.1007\/978-3-662-49630-5_13","DOI":"10.1007\/978-3-662-49630-5_13"},{"key":"1351_CR59","doi-asserted-by":"publisher","unstructured":"Chatterjee, K., Ibsen-Jensen, R.: The complexity of ergodic mean-payoff games, in Automata, languages, and programming. Part II. In: Lecture Notes in Comput. Sci., vol. 8573, pp. 122\u2013133. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43951-7_11","DOI":"10.1007\/978-3-662-43951-7_11"},{"key":"1351_CR60","doi-asserted-by":"publisher","unstructured":"Etessami, K., Yannakakis, M.: Recursive Concurrent Stochastic Games, in Automata. Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II, In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I.: (eds.), Lecture Notes in Computer Science, vol. 4052, pp. 324\u2013335. Springer, Berlin (2006). https:\/\/doi.org\/10.1007\/11787006_28","DOI":"10.1007\/11787006_28"},{"key":"1351_CR61","doi-asserted-by":"publisher","unstructured":"Etessami, K., Yannakakis, M.: Recursive concurrent stochastic games. Log. Methods Comput. Sci. 4(4), 4:7, 21 (2008). https:\/\/doi.org\/10.2168\/LMCS-4(4:7)2008","DOI":"10.2168\/LMCS-4(4:7)2008"},{"key":"1351_CR62","doi-asserted-by":"publisher","unstructured":"Hansen, K.A.: The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games. In: Algorithmic Game Theory - 10th International Symposium, SAGT 2017, L\u2019Aquila, Italy, September 12-14, 2017, Proceedings, Lecture Notes in Computer Science, In: Bil\u00f2, V., Flammini, M. (eds.), vol. 10504, pp. 119\u2013130. Springer, Berlin (2017). https:\/\/doi.org\/10.1007\/978-3-319-66700-3_10","DOI":"10.1007\/978-3-319-66700-3_10"},{"issue":"7","key":"1351_CR63","doi-asserted-by":"publisher","first-page":"1554","DOI":"10.1007\/s00224-018-9887-9","volume":"63","author":"KA Hansen","year":"2019","unstructured":"Hansen, K.A.: The real computational complexity of minmax value and equilibrium refinements in multi-player games. Theory Comput. Syst. 63(7), 1554\u20131571 (2019). https:\/\/doi.org\/10.1007\/s00224-018-9887-9","journal-title":"Theory Comput. Syst."},{"key":"1351_CR64","unstructured":"Hansen, K.A., S\u00f8lvsten, S.C.: Existential theory of the reals completeness of stationary nash equilibria in perfect information stochastic games. CoRR arXiv:2006.08314 (2020). https:\/\/arxiv.org\/abs\/2006.08314"},{"issue":"2","key":"1351_CR65","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/s00224-015-9662-0","volume":"60","author":"M Schaefer","year":"2017","unstructured":"Schaefer, M., \u0160tefankovi\u010d, D.: Fixed points, Nash equilibria, and the existential theory of the reals. Theory Comput. Syst. 60(2), 172\u2013193 (2017). https:\/\/doi.org\/10.1007\/s00224-015-9662-0","journal-title":"Theory Comput. Syst."},{"key":"1351_CR66","unstructured":"Abrahamsen, M., Kleist, L., Miltzow, T.: Training neural networks is ER-complete. In: Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, pp. 18293\u201318306 (2021). https:\/\/proceedings.neurips.cc\/paper\/2021\/hash\/9813b270ed0288e7c0388f0fd4ec68f5-Abstract.html"},{"key":"1351_CR67","unstructured":"Bertschinger, D., Hertrich, C., Jungeblut, P., Miltzow, T., Weber, S.: Training Fully Connected Neural Networks is $$\\exists $$R-Complete. In: Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, In: Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., Levine S. (eds.), (2023). http:\/\/papers.nips.cc\/paper_files\/paper\/2023\/hash\/71c31ebf577ffdad5f4a74156daad518-Abstract-Conference.html"},{"key":"1351_CR68","unstructured":"Boege, T.: The gaussian conditional independence inference problem. Ph.D. thesis, Universit\u00e4t Magdeburg (2022)"},{"issue":"1","key":"1351_CR69","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1017\/S1755020322000211","volume":"17","author":"M Moss\u00e9","year":"2024","unstructured":"Moss\u00e9, M., Ibeling, D., Icard, T.: Is causal reasoning harder than probabilistic reasoning? Rev. Symb. Log. 17(1), 106\u2013131 (2024). https:\/\/doi.org\/10.1017\/S1755020322000211","journal-title":"Rev. Symb. Log."},{"key":"1351_CR70","doi-asserted-by":"publisher","unstructured":"Laurent, M.: Matrix Completion Problems. In: Encyclopedia of Optimization, pp. 1967\u20131975. Springer, US, Boston, MA (2009). https:\/\/doi.org\/10.1007\/978-0-387-74759-0_355","DOI":"10.1007\/978-0-387-74759-0_355"},{"issue":"5","key":"1351_CR71","doi-asserted-by":"publisher","first-page":"1161","DOI":"10.1007\/s00224-017-9800-y","volume":"62","author":"M Schaefer","year":"2018","unstructured":"Schaefer, M., \u0160tefankovi\u010d, D.: The complexity of tensor rank. Theory Comput. Syst. 62(5), 1161\u20131174 (2018). https:\/\/doi.org\/10.1007\/s00224-017-9800-y","journal-title":"Theory Comput. Syst."},{"key":"1351_CR72","doi-asserted-by":"publisher","unstructured":"Shitov, Y.: A universality theorem for nonnegative matrix factorizations. CoRR arXiv:1606.09068 (2016). https:\/\/doi.org\/10.48550\/arXiv.1606.09068","DOI":"10.48550\/arXiv.1606.09068"},{"issue":"3","key":"1351_CR73","doi-asserted-by":"publisher","first-page":"1898","DOI":"10.1137\/16M1080616","volume":"27","author":"Y Shitov","year":"2017","unstructured":"Shitov, Y.: The complexity of positive semidefinite matrix factorization. SIAM J. Optim. 27(3), 1898\u20131909 (2017). https:\/\/doi.org\/10.1137\/16M1080616","journal-title":"SIAM J. Optim."},{"key":"1351_CR74","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-023-09610-1","author":"Y Shitov","year":"2023","unstructured":"Shitov, Y.: Further $$\\exists \\mathbb{R} $$-complete problems with PSD matrix factorizations. Found. Comput. Math. (2023). https:\/\/doi.org\/10.1007\/s10208-023-09610-1","journal-title":"Found. Comput. Math."},{"key":"1351_CR75","doi-asserted-by":"publisher","unstructured":"Miltzow, T., Schmiermann, R.F.: On classifying continuous constraint satisfaction problems. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science\u2014FOCS 2021, pp. 781\u2013791. IEEE Computer Soc., Los Alamitos, CA, (2022). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00081","DOI":"10.1109\/FOCS52979.2021.00081"},{"key":"1351_CR76","doi-asserted-by":"publisher","DOI":"10.46298\/THEORETICS.24.10","author":"T Miltzow","year":"2024","unstructured":"Miltzow, T., Schmiermann, R.F.: On classifying continuous constraint satisfaction problems. TheoretiCS (2024). https:\/\/doi.org\/10.46298\/THEORETICS.24.10","journal-title":"TheoretiCS"},{"key":"1351_CR77","doi-asserted-by":"publisher","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: The art gallery problem is $$\\exists \\mathbb{R}$$-complete. In: STOC\u201918\u2014Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 65\u201373. ACM, New York (2018). https:\/\/doi.org\/10.1145\/3188745.3188868","DOI":"10.1145\/3188745.3188868"},{"issue":"1","key":"1351_CR78","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/3486220","volume":"69","author":"M Abrahamsen","year":"2022","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: The art gallery problem is $$\\exists \\mathbb{R} $$-complete. J. ACM 69(1), 41\u2013470 (2022). https:\/\/doi.org\/10.1145\/3486220","journal-title":"J. ACM"},{"key":"1351_CR79","doi-asserted-by":"publisher","unstructured":"Stade, J.: Complexity of the boundary-guarding art gallery problem. CoRR arXiv:2210.12817 (2022). https:\/\/doi.org\/10.48550\/arXiv.2210.12817","DOI":"10.48550\/arXiv.2210.12817"},{"key":"1351_CR80","doi-asserted-by":"publisher","unstructured":"Abrahamsen, M., Miltzow, T., Seiferth, N.: Framework for ER-completeness of two-dimensional packing problems. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, pp. 1014\u20131021. IEEE Computer Soc (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00098","DOI":"10.1109\/FOCS46700.2020.00098"},{"key":"1351_CR81","doi-asserted-by":"publisher","unstructured":"Abrahamsen, M.: Covering polygons is even harder. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science\u2014FOCS 2021, pp. 375\u2013386. IEEE Computer Soc (2022). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00045","DOI":"10.1109\/FOCS52979.2021.00045"},{"key":"1351_CR82","doi-asserted-by":"publisher","unstructured":"Blanc, M., Hansen, K.A.: Computational complexity of multi-player evolutionarily stable strategies. In: Computer science\u2014theory and applications, Lecture Notes in Comput. Sci, vol. 12730, pp. 1\u201317. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-79416-3_1","DOI":"10.1007\/978-3-030-79416-3_1"},{"key":"1351_CR83","doi-asserted-by":"publisher","unstructured":"B\u00fcrgisser, P., Cucker, F.: Exotic Quantifiers, Complexity Classes, and Complete Problems. In: Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings, Lecture Notes in Computer Science, In: Arge, L., Cachin, C., Jurdzinski, T., Tarlecki, A. (eds.), vol. 4596, pp. 207\u2013218. Springer, Berlin (2007). https:\/\/doi.org\/10.1007\/978-3-540-73420-8_20","DOI":"10.1007\/978-3-540-73420-8_20"},{"issue":"2","key":"1351_CR84","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s10208-007-9006-9","volume":"9","author":"P B\u00fcrgisser","year":"2009","unstructured":"B\u00fcrgisser, P., Cucker, F.: Exotic quantifiers, complexity classes, and complete problems. Found. Comput. Math. 9(2), 135\u2013170 (2009). https:\/\/doi.org\/10.1007\/s10208-007-9006-9","journal-title":"Found. Comput. Math."},{"key":"1351_CR85","doi-asserted-by":"publisher","unstructured":"D\u2019Costa, J., Lefaucheux, E., Neumann, E., Ouaknine, J., Worrell, J.: On the complexity of the escape problem for linear dynamical systems over compact semialgebraic sets. In: 46th International Symposium on Mathematical Foundations of Computer Science, LIPIcs, vol. 202, p. 21. Schloss Dagstuhl. Leibniz-Zent. Inform, Wadern (2021). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2021.33","DOI":"10.4230\/LIPIcs.MFCS.2021.33"},{"key":"1351_CR86","doi-asserted-by":"publisher","unstructured":"Jungeblut, P., Kleist, L., Miltzow, T.: The complexity of the Hausdorff distance. In: 38th International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform, vol. 224, p. 17. Schloss Dagstuhl. Leibniz-Zent. Inform, Wadern (2022). https:\/\/doi.org\/10.4230\/lipics.socg.2022.48","DOI":"10.4230\/lipics.socg.2022.48"},{"issue":"1","key":"1351_CR87","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/S00454-023-00562-5","volume":"71","author":"P Jungeblut","year":"2024","unstructured":"Jungeblut, P., Kleist, L., Miltzow, T.: The complexity of the Hausdorff distance. Discret. Comput. Geom. 71(1), 177\u2013213 (2024). https:\/\/doi.org\/10.1007\/S00454-023-00562-5","journal-title":"Discret. Comput. Geom."},{"issue":"2","key":"1351_CR88","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/S00224-023-10151-X","volume":"68","author":"M Schaefer","year":"2024","unstructured":"Schaefer, M., Stefankovic, D.: Beyond the existential theory of the reals. Theory Comput. Syst. 68(2), 195\u2013226 (2024). https:\/\/doi.org\/10.1007\/S00224-023-10151-X","journal-title":"Theory Comput. Syst."},{"key":"1351_CR89","unstructured":"Richter-Gebert, J.: Mn\u00ebv\u2019s universality theorem revisited. S\u00e9minaire Lotharingien de Combinatoire [electronic only] 34, 15\u201315 (1995). http:\/\/eudml.org\/doc\/119012"},{"key":"1351_CR90","doi-asserted-by":"publisher","unstructured":"Biedl, T.C., Kaufmann, M.: Area-Efficient Static and Incremental Graph Drawings. In: Algorithms - ESA \u201997, 5th Annual European Symposium, Graz, Austria, September 15-17, 1997, Proceedings, Lecture Notes in Computer Science, In: Burkard, R.E., Woeginger, G.J. (eds.), vol. 1284, pp. 37\u201352. Springer, Berlin (1997). https:\/\/doi.org\/10.1007\/3-540-63397-9_4","DOI":"10.1007\/3-540-63397-9_4"},{"key":"1351_CR91","doi-asserted-by":"publisher","unstructured":"Bra\u00df, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S.G., Lubiw, A., Mitchell, J.S.B.: On Simultaneous Planar Graph Embeddings. In: Algorithms and Data Structures, 8th International Workshop, WADS 2003, Ottawa, Ontario, Canada, July 30 - August 1, 2003, Proceedings, Lecture Notes in Computer Science, In: Dehne, F.K.H.A., Sack, J., Smid, M.H.M. (eds.), vol. 2748, pp. 243\u2013255. Springer, Berlin (2003). https:\/\/doi.org\/10.1007\/978-3-540-45078-8_22","DOI":"10.1007\/978-3-540-45078-8_22"},{"issue":"2","key":"1351_CR92","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/J.COMGEO.2006.05.006","volume":"36","author":"P Bra\u00df","year":"2007","unstructured":"Bra\u00df, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S.G., Lubiw, A., Mitchell, J.S.B.: On simultaneous planar graph embeddings. Comput. Geom. 36(2), 117\u2013130 (2007). https:\/\/doi.org\/10.1016\/J.COMGEO.2006.05.006","journal-title":"Comput. Geom."},{"issue":"2","key":"1351_CR93","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1016\/0095-8956(86)90048-1","volume":"41","author":"ML Vergnas","year":"1986","unstructured":"Vergnas, M.L.: Order properties of lines in the plane and a conjecture of G. Ringel. J. Comb. Theory, Ser. B 41(2), 246\u2013249 (1986). https:\/\/doi.org\/10.1016\/0095-8956(86)90048-1","journal-title":"Ringel. J. Comb. Theory, Ser. B"},{"key":"1351_CR94","doi-asserted-by":"publisher","unstructured":"Chan, T.M., Frati, F., Gutwenger, C., Lubiw, A., Mutzel, P., Schaefer, M.: Drawing Partially Embedded and Simultaneously Planar Graphs. In: Graph Drawing - 22nd International Symposium, GD 2014, W\u00fcrzburg, Germany, September 24-26, 2014, Revised Selected Papers, Lecture Notes in Computer Science, In: Duncan, C.A., Symvonis, A. (eds.), vol. 8871, pp. 25\u201339. Springer, Berlin (2014). https:\/\/doi.org\/10.1007\/978-3-662-45803-7_3","DOI":"10.1007\/978-3-662-45803-7_3"},{"issue":"2","key":"1351_CR95","doi-asserted-by":"publisher","first-page":"681","DOI":"10.7155\/JGAA.00375","volume":"19","author":"TM Chan","year":"2015","unstructured":"Chan, T.M., Frati, F., Gutwenger, C., Lubiw, A., Mutzel, P., Schaefer, M.: Drawing partially embedded and simultaneously planar graphs. J. Graph Algorithms Appl. 19(2), 681\u2013706 (2015). https:\/\/doi.org\/10.7155\/JGAA.00375","journal-title":"J. Graph Algorithms Appl."},{"key":"1351_CR96","doi-asserted-by":"publisher","DOI":"10.1016\/s0304-0208(08)x7180-4","volume-title":"Planar Graphs: Theory and Algorithms","author":"T Nishizeki","year":"1988","unstructured":"Nishizeki, T., Chiba, N.: Planar Graphs: Theory and Algorithms. Elsevier, Amsterdam (1988). https:\/\/doi.org\/10.1016\/s0304-0208(08)x7180-4"},{"key":"1351_CR97","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1090\/S0002-9947-1932-1501641-2","volume":"34","author":"H Whitney","year":"1932","unstructured":"Whitney, H.: Non-separable and planar graphs. Trans. Am. Math. Soc. 34, 339\u2013362 (1932)","journal-title":"Trans. Am. Math. Soc."},{"key":"1351_CR98","doi-asserted-by":"publisher","unstructured":"Hutchinson, J.P., Shermer, T.C., Vince, A.: On Representations of Some Thickness-Two Graphs. In: Graph Drawing, Symposium on Graph Drawing, GD \u201995, Passau, Germany, September 20-22, 1995, Proceedings, Lecture Notes in Computer Science, In: Brandenburg, F. (ed.), vol. 1027, pp. 324\u2013332. Springer, Berlin (1995). https:\/\/doi.org\/10.1007\/BFB0021815","DOI":"10.1007\/BFB0021815"},{"issue":"3","key":"1351_CR99","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/S0925-7721(99)00018-8","volume":"13","author":"J Hutchinson","year":"1999","unstructured":"Hutchinson, J., Shermer, T., Vince, A.: On representations of some thickness-two graphs. Comput. Geom. 13(3), 161\u2013171 (1999). https:\/\/doi.org\/10.1016\/S0925-7721(99)00018-8","journal-title":"Comput. Geom."},{"issue":"3","key":"1351_CR100","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1023\/A:1021231927255","volume":"19","author":"O Aichholzer","year":"2002","unstructured":"Aichholzer, O., Aurenhammer, F., Krasser, H.: Enumerating order types for small point sets with applications. Order 19(3), 265\u2013281 (2002). https:\/\/doi.org\/10.1023\/A:1021231927255","journal-title":"Order"},{"key":"1351_CR101","unstructured":"OEIS. Number of simple arrangements of $$n$$ pseudolines in the projective plane with a marked cell. Number of Euclidean pseudo-order types: nondegenerate abstract order types of configurations of $$n$$ points in the plane (2023). https:\/\/oeis.org\/A006247. [Online; accessed on 2023-09-15]"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01351-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01351-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01351-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T05:11:34Z","timestamp":1770009094000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01351-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,10]]},"references-count":101,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["1351"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01351-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,10]]},"assertion":[{"value":"24 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 November 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"3"}}