{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:13:45Z","timestamp":1778498025462,"version":"3.51.4"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,5,18]],"date-time":"2022-05-18T00:00:00Z","timestamp":1652832000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,18]],"date-time":"2022-05-18T00:00:00Z","timestamp":1652832000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["016.Veni.192.250"],"award-info":[{"award-number":["016.Veni.192.250"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\exists \\mathbb {R}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>\u2203<\/mml:mo>\n                    <mml:mi>R<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> plays a crucial role in the study of geometric problems. Sometimes <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\exists \\mathbb {R}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>\u2203<\/mml:mo>\n                    <mml:mi>R<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is referred to as the \u2018real analog\u2019 of\u00a0<jats:sc>NP<\/jats:sc>. While <jats:sc>NP<\/jats:sc> is a class of computational problems that deals with existentially quantified <jats:italic>boolean<\/jats:italic> variables, <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\exists \\mathbb {R}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>\u2203<\/mml:mo>\n                    <mml:mi>R<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> deals with existentially quantified <jats:italic>real<\/jats:italic> variables. In analogy to <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Pi _2^p$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msubsup>\n                    <mml:mi>\u03a0<\/mml:mi>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mi>p<\/mml:mi>\n                  <\/mml:msubsup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Sigma _2^p$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msubsup>\n                    <mml:mi>\u03a3<\/mml:mi>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mi>p<\/mml:mi>\n                  <\/mml:msubsup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in the famous polynomial hierarchy, we study the complexity classes <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\forall \\exists \\mathbb {R}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>\u2200<\/mml:mo>\n                    <mml:mo>\u2203<\/mml:mo>\n                    <mml:mi>R<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:tex-math>$$ \\exists \\forall \\mathbb {R}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>\u2203<\/mml:mo>\n                    <mml:mo>\u2200<\/mml:mo>\n                    <mml:mi>R<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with <jats:italic>real<\/jats:italic> variables. Our main interest is the <jats:sc>Area<\/jats:sc><jats:sc>Universality<\/jats:sc> problem, where we are given a plane graph\u00a0<jats:italic>G<\/jats:italic>, and ask if for each assignment of areas to the inner faces of <jats:italic>G<\/jats:italic>, there exists a straight-line drawing of <jats:italic>G<\/jats:italic> realizing the assigned areas. We conjecture that <jats:sc>Area<\/jats:sc><jats:sc>Universality<\/jats:sc> is <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\forall \\exists \\mathbb {R}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>\u2200<\/mml:mo>\n                    <mml:mo>\u2203<\/mml:mo>\n                    <mml:mi>R<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete and support this conjecture by proving <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\exists \\mathbb {R}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>\u2203<\/mml:mo>\n                    <mml:mi>R<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>- and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\forall \\exists \\mathbb {R}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>\u2200<\/mml:mo>\n                    <mml:mo>\u2203<\/mml:mo>\n                    <mml:mi>R<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-completeness of two variants of <jats:sc>Area<\/jats:sc><jats:sc>Universality<\/jats:sc>. To this end, we introduce tools to prove <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\forall \\exists \\mathbb {R}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>\u2200<\/mml:mo>\n                    <mml:mo>\u2203<\/mml:mo>\n                    <mml:mi>R<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hardness and membership. Finally, we present geometric problems as candidates for <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\forall \\exists \\mathbb {R}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>\u2200<\/mml:mo>\n                    <mml:mo>\u2203<\/mml:mo>\n                    <mml:mi>R<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.<\/jats:p>","DOI":"10.1007\/s00454-022-00381-0","type":"journal-article","created":{"date-parts":[[2022,5,18]],"date-time":"2022-05-18T15:06:58Z","timestamp":1652886418000},"page":"154-188","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Completeness for the Complexity Class $$\\forall \\exists \\mathbb {R}$$ and Area-Universality"],"prefix":"10.1007","volume":"70","author":[{"given":"Michael Gene","family":"Dobbins","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3786-916X","authenticated-orcid":false,"given":"Linda","family":"Kleist","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tillmann","family":"Miltzow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Rz\u0105\u017cewski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,5,18]]},"reference":[{"key":"381_CR1","doi-asserted-by":"crossref","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: The art gallery problem is $$\\exists \\mathbb{R}$$-complete. In: 50th Annual ACM SIGACT Symposium on Theory of Computing (Los Angeles 2018), pp. 65\u201373. ACM, New York (2018)","DOI":"10.1145\/3188745.3188868"},{"key":"381_CR2","unstructured":"Abrahamsen, M., Kleist, L., Miltzow, T.: Training neural networks is $$\\exists {\\mathbb{R} }$$-complete (2021). arXiv:2102.09798"},{"key":"381_CR3","unstructured":"Abrahamsen, M., Miltzow, T.: Dynamic toolbox for ETRINV (2019). arXiv:1912.08674"},{"key":"381_CR4","doi-asserted-by":"crossref","unstructured":"Abrahamsen, M., Miltzow, T., Seiferth, N.: Framework for ER-completeness of two-dimensional packing problems. In: 61st Annual Symposium on Foundations of Computer Science, pp. 1014\u20131021. IEEE, Los Alamitos (2020)","DOI":"10.1109\/FOCS46700.2020.00098"},{"key":"381_CR5","doi-asserted-by":"crossref","unstructured":"Akitaya, H.A., Fulek, R., T\u00f3th, C.D.: Recognizing weak embeddings of graphs. ACM Trans. Algorithms 15(4), #\u00a050 (2019)","DOI":"10.1145\/3344549"},{"key":"381_CR6","doi-asserted-by":"crossref","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol. 10. Springer, Berlin (2006)","DOI":"10.1007\/3-540-33099-2"},{"issue":"2","key":"381_CR7","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s00454-006-1285-4","volume":"37","author":"M Belk","year":"2007","unstructured":"Belk, M.: Realizability of graphs in three dimensions. Discrete Comput. Geom. 37(2), 139\u2013162 (2007)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"381_CR8","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s00454-006-1284-5","volume":"37","author":"M Belk","year":"2007","unstructured":"Belk, M., Connelly, R.: Realizability of graphs. Discrete Comput. Geom. 37(2), 125\u2013137 (2007)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"381_CR9","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1016\/j.comgeo.2012.09.004","volume":"46","author":"T Biedl","year":"2013","unstructured":"Biedl, T., Ruiz Vel\u00e1zquez, L.E.: Drawing planar $$3$$-trees with given face areas. Comput. Geom. 46(3), 276\u2013285 (2013)","journal-title":"Comput. Geom."},{"key":"381_CR10","volume-title":"Complexity and Real Computation","author":"L Blum","year":"2012","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, New York (2012)"},{"issue":"1","key":"381_CR11","doi-asserted-by":"publisher","first-page":"79","DOI":"10.7155\/jgaa.00218","volume":"15","author":"S Cabello","year":"2011","unstructured":"Cabello, S., van Kreveld, M., Liotta, G., Meijer, H., Speckmann, B., Verbeek, K.: Geometric simultaneous embeddings of a graph and a matching. J. Graph Algorithms Appl. 15(1), 79\u201396 (2011)","journal-title":"J. Graph Algorithms Appl."},{"key":"381_CR12","doi-asserted-by":"crossref","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 (Eindhoven 2017). Lecture Notes in Computer Science, vol. 10520, pp. 153\u2013166. Springer, Cham (2017)","DOI":"10.1007\/978-3-319-68705-6_12"},{"issue":"2","key":"381_CR13","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s00454-003-0006-7","volume":"30","author":"R Connelly","year":"2003","unstructured":"Connelly, R., Demaine, E.D., Rote, G.: Straightening polygonal arcs and convexifying polygonal cycles. Discrete Comput. Geom. 30(2), 205\u2013239 (2003)","journal-title":"Discrete Comput. Geom."},{"key":"381_CR14","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: 3rd Annual ACM Symposium on Theory of Computing (Shaker Heights 1971), pp. 151\u2013158. ACM, New York (1971)","DOI":"10.1145\/800157.805047"},{"key":"381_CR15","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, Ch.H.: The complexity of computing a Nash equilibrium. In: 38th Annual ACM Symposium on Theory of Computing (Seattle 2006), pp. 71\u201378. ACM, New York (2006)","DOI":"10.1145\/1132516.1132527"},{"issue":"1\u20132","key":"381_CR16","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0747-7171(88)80004-X","volume":"5","author":"JH Davenport","year":"1988","unstructured":"Davenport, J.H., Heintz, J.: Real quantifier elimination is doubly exponential. J. Symb. Comput. 5(1\u20132), 29\u201335 (1988)","journal-title":"J. Symb. Comput."},{"key":"381_CR17","doi-asserted-by":"crossref","unstructured":"Dobbins, M.G., Kleist, L., Miltzow, T., Rz\u0105\u017cewski, P.: $$\\forall \\exists \\mathbb{R}$$-completeness and area-universality. In: Graph-Theoretic Concepts in Computer Science (Cottbus 2018). Lecture Notes in Computer Science, vol. 11159, pp. 164\u2013175. Springer, Cham (2018)","DOI":"10.1007\/978-3-030-00256-5_14"},{"issue":"1","key":"381_CR18","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.ejc.2004.01.003","volume":"26","author":"Z Dvo\u0159\u00e1k","year":"2005","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1l\u2019, D., \u0160krekovski, R.: Coloring face hypergraphs on surfaces. Eur. J. Comb. 26(1), 95\u2013110 (2005)","journal-title":"Eur. J. Comb."},{"issue":"3","key":"381_CR19","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1137\/110834032","volume":"41","author":"D Eppstein","year":"2012","unstructured":"Eppstein, D., Mumford, E., Speckmann, B., Verbeek, K.: Area-universal and constrained rectangular layouts. SIAM J. Comput. 41(3), 537\u2013564 (2012)","journal-title":"SIAM J. Comput."},{"key":"381_CR20","doi-asserted-by":"crossref","unstructured":"Erickson, J., van der Hoog, I., Miltzow, T.: Smoothing the gap between NP and ER. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, pp. 1022\u20131033. IEEE, Los Alamitos (2020)","DOI":"10.1109\/FOCS46700.2020.00099"},{"key":"381_CR21","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.comgeo.2017.06.010","volume":"68","author":"W Evans","year":"2018","unstructured":"Evans, W., Felsner, S., Kaufmann, M., Kobourov, S.G., Mondal, D., Nishat, R.I., Verbeek, K.: Table cartogram. Comput. Geom. 68, 174\u2013185 (2018)","journal-title":"Comput. Geom."},{"issue":"1","key":"381_CR22","doi-asserted-by":"publisher","first-page":"171","DOI":"10.7155\/jgaa.00555","volume":"25","author":"W Evans","year":"2021","unstructured":"Evans, W., Felsner, S., Kleist, L., Kobourov, S.: On area-universal quadrangulations. J. Graph Algorithms Appl. 25(1), 171\u2013193 (2021)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"381_CR23","doi-asserted-by":"publisher","first-page":"233","DOI":"10.7155\/jgaa.00320","volume":"18","author":"S Felsner","year":"2014","unstructured":"Felsner, S.: Exploiting air-pressure to map floorplans on point sets. J. Graph Algorithms Appl. 18(2), 233\u2013252 (2014)","journal-title":"J. Graph Algorithms Appl."},{"key":"381_CR24","unstructured":"Henning, H.: Ans\u00e4tze zur Entscheidung von Fl\u00e4chenuniversalit\u00e4t. MSc thesis, Technische Universit\u00e4t Berlin (2018). www.math.tu-berlin.de\/~felsner\/Diplomarbeiten\/heinrich.pdf"},{"issue":"3","key":"381_CR25","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1007\/s00454-012-9394-8","volume":"47","author":"RJ Kang","year":"2012","unstructured":"Kang, R.J., M\u00fcller, T.: Sphere and dot product representations of graphs. Discrete Comput. Geom. 47(3), 548\u2013568 (2012)","journal-title":"Discrete Comput. Geom."},{"key":"381_CR26","doi-asserted-by":"crossref","unstructured":"Kleist, L.: Drawing planar graphs with prescribed face areas. In: Graph-Theoretic Concepts in Computer Science (Istanbul 2016). Lecture Notes in Computer Science, vol. 9941, pp. 158\u2013170. Springer, Berlin (2016)","DOI":"10.1007\/978-3-662-53536-3_14"},{"issue":"1","key":"381_CR27","first-page":"290","volume":"9","author":"L Kleist","year":"2018","unstructured":"Kleist, L.: Drawing planar graphs with prescribed face areas. J. Comput. Geom. 9(1), 290\u2013311 (2018)","journal-title":"J. Comput. Geom."},{"key":"381_CR28","doi-asserted-by":"publisher","unstructured":"Kleist, L.: Planar Graphs and Face Areas\u2014Area-Universality. PhD thesis, Technische Universit\u00e4t Berlin (2018). https:\/\/doi.org\/10.14279\/depositonce-7674","DOI":"10.14279\/depositonce-7674"},{"key":"381_CR29","doi-asserted-by":"crossref","unstructured":"Kleist, L.: On the area-universality of triangulations. In: Graph Drawing and Network Visualization (Barcelona 2018). Lecture Notes in Computer Science, vol. 11282, pp. 333\u2013346. Springer, Cham (2018)","DOI":"10.1007\/978-3-030-04414-5_23"},{"key":"381_CR30","unstructured":"Levin, L.A.: Universal sequential search problems. Probl. Peredachi Inf. 9(3), 115\u2013116 (1973). (in Russian)"},{"key":"381_CR31","doi-asserted-by":"crossref","unstructured":"Lubiw, A., Miltzow, T., Mondal, D.: The complexity of drawing a graph in a polygonal region. In: Graph Drawing and Network Visualization (Barcelona 2018). Lecture Notes in Computer Science, vol. 11282, pp. 387\u2013401. Springer, Cham (2018)","DOI":"10.1007\/978-3-030-04414-5_28"},{"key":"381_CR32","unstructured":"Matou\u0161ek, J.: Intersection graphs of segments and $$\\exists {\\mathbb{R}} $$ (2014). arXiv:1406.2636"},{"issue":"1","key":"381_CR33","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.jctb.2012.09.004","volume":"103","author":"C McDiarmid","year":"2013","unstructured":"McDiarmid, C., M\u00fcller, T.: Integer realizations of disk and segment graphs. J. Comb. Theory Ser. B 103(1), 114\u2013143 (2013)","journal-title":"J. Comb. Theory Ser. B"},{"key":"381_CR34","unstructured":"Meister, A.L.F.: Generalia de genesi figurarum planarum et inde pendentibus earum affectionibus. Novi Commentarii Societatis Regiae Scientiarum Gottingensis 1, 144\u2013180 (1769\/1770)"},{"key":"381_CR35","unstructured":"Miltzow, T.: Augmenting a geometric matching is $$NP$$-complete (2012). arXiv:1206.6360"},{"key":"381_CR36","doi-asserted-by":"crossref","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 Mathematics, vol. 1346, pp. 527\u2013543. Springer, Berlin (1988)","DOI":"10.1007\/BFb0082792"},{"key":"381_CR37","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2001)"},{"key":"381_CR38","unstructured":"Muller, C.: Excluded Minors for Isometric Embeddings of Graphs in $$\\ell _\\infty ^k$$-Spaces. MSc thesis, Universit\u00e9 Libre de Bruxelles (2017)"},{"key":"381_CR39","volume-title":"An Introduction to Game Theory","author":"MJ Osborne","year":"2003","unstructured":"Osborne, M.J.: An Introduction to Game Theory. Oxford University Press, New York (2003)"},{"key":"381_CR40","unstructured":"Richter-Gebert, J.: Mn\u00ebv\u2019s universality theorem revisited. S\u00e9m. Lothar. Combin. 34, #\u00a0B34h (1995)"},{"issue":"4","key":"381_CR41","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. 32(4), 403\u2013412 (1995)","journal-title":"Bull. Am. Math. Soc."},{"key":"381_CR42","unstructured":"Ringel, G.: Equiareal graphs. In: Contemporary Methods in Graph Theory, pp. 503\u2013505. Bibliographisches Inst., Mannheim (1990)"},{"issue":"2","key":"381_CR43","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Comb. Theory Ser. B 92(2), 325\u2013357 (2004)","journal-title":"J. Comb. Theory Ser. B"},{"key":"381_CR44","doi-asserted-by":"crossref","unstructured":"Schaefer, M.: Complexity of some geometric and topological problems. In: Graph Drawing (Chicago 2009). Lecture Notes in Computer Science, vol. 5849, pp. 334\u2013344. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-11805-0_32"},{"key":"381_CR45","doi-asserted-by":"crossref","unstructured":"Schaefer, M.: Realizability of graphs and linkages. In: Thirty Essays on Geometric Graph Theory, pp. 461\u2013482. Springer, New York (2013)","DOI":"10.1007\/978-1-4614-0110-0_24"},{"issue":"2","key":"381_CR46","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\u0107, D.: Fixed points, Nash equilibria, and the existential theory of the reals. Theory Comput. Syst. 60(2), 172\u2013193 (2017)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"381_CR47","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1017\/S0963548300000407","volume":"1","author":"C Thomassen","year":"1992","unstructured":"Thomassen, C.: Plane cubic graphs with prescribed face areas. Comb. Probab. Comput. 1(4), 371\u2013381 (1992)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"381_CR48","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1109\/31.1739","volume":"35","author":"Sh Wimer","year":"1988","unstructured":"Wimer, Sh., Koren, I., Cederbaum, I.: Floorplans, planar graphs, and layouts. IEEE Trans. Circuits Syst. 35(3), 267\u2013278 (1988)","journal-title":"IEEE Trans. Circuits Syst."},{"key":"381_CR49","unstructured":"Intercept Theorem. In: Wikipedia, the Free Encyclopedia. https:\/\/en.wikipedia.org\/wiki\/Intercept_theorem"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00381-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00381-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00381-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,6]],"date-time":"2023-06-06T18:53:55Z","timestamp":1686077635000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00381-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,18]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["381"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00381-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,18]]},"assertion":[{"value":"6 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 December 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}