{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,13]],"date-time":"2025-12-13T06:57:29Z","timestamp":1765609049670,"version":"3.40.3"},"publisher-location":"Cham","reference-count":57,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031492716"},{"type":"electronic","value":"9783031492723"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-49272-3_12","type":"book-chapter","created":{"date-parts":[[2024,1,11]],"date-time":"2024-01-11T09:04:34Z","timestamp":1704963874000},"page":"163-179","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Complexity of\u00a0Recognizing Geometric Hypergraphs"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Bertschinger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1037-0203","authenticated-orcid":false,"given":"Nicolas","family":"El Maalouly","sequence":"additional","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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4563-2864","authenticated-orcid":false,"given":"Tillmann","family":"Miltzow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1901-3621","authenticated-orcid":false,"given":"Simon","family":"Weber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,1,1]]},"reference":[{"key":"12_CR1","doi-asserted-by":"publisher","unstructured":"Abrahamsen, M.: Covering polygons is even harder. In: IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS 2022), pp. 375\u2013386 (2022). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00045","DOI":"10.1109\/FOCS52979.2021.00045"},{"key":"12_CR2","doi-asserted-by":"publisher","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: The art gallery problem is $$\\exists \\mathbb{R} $$-complete. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pp. 65\u201373 (2018). https:\/\/doi.org\/10.1145\/3188745.3188868","DOI":"10.1145\/3188745.3188868"},{"key":"12_CR3","unstructured":"Abrahamsen, M., Kleist, L., Miltzow, T.: Training neural networks is $$\\exists \\mathbb{R}$$-complete. In: Advances in Neural Information Processing Systems (NeurIPS 2021), vol.\u00a034, pp. 18293\u201318306 (2021). https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2021\/file\/9813b270ed0288e7c0388f0fd4ec68f5-Paper.pdf"},{"key":"12_CR4","doi-asserted-by":"publisher","unstructured":"Abrahamsen, M., Kleist, L., Miltzow, T.: Geometric embeddability of complexes is $$\\exists \\mathbb{R} $$-complete. In: Symposium on Computational Geometry (SOCG 2023) (2023, to appear). https:\/\/doi.org\/10.48550\/arXiv.2108.02585","DOI":"10.48550\/arXiv.2108.02585"},{"key":"12_CR5","doi-asserted-by":"publisher","unstructured":"Abrahamsen, M., Miltzow, T., Seiferth, N.: Framework for $$\\exists \\mathbb{R} $$-completeness of two-dimensional packing problems. In: IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS 2020), pp. 1014\u20131021 (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00098","DOI":"10.1109\/FOCS46700.2020.00098"},{"issue":"7","key":"12_CR6","doi-asserted-by":"publisher","first-page":"3248","DOI":"10.1137\/090762968","volume":"39","author":"B Aronov","year":"2010","unstructured":"Aronov, B., Ezra, E., Sharir, M.: Small-size $$\\epsilon $$-nets for axis-parallel rectangles and boxes. SIAM J. Comput. (SiComp) 39(7), 3248\u20133282 (2010). https:\/\/doi.org\/10.1137\/090762968","journal-title":"SIAM J. Comput. (SiComp)"},{"key":"12_CR7","doi-asserted-by":"publisher","unstructured":"Axenovich, M., Ueckerdt, T.: Density of range capturing hypergraphs. J. Comput. Geom. (JoCG) 7(1) (2016). https:\/\/doi.org\/10.20382\/jocg.v7i1a1","DOI":"10.20382\/jocg.v7i1a1"},{"key":"12_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-030-30473-7_11","volume-title":"Algorithmic Game Theory","author":"MLT Berthelsen","year":"2019","unstructured":"Berthelsen, M.L.T., Hansen, K.A.: On the computational complexity of decision problems about multi-player nash equilibria. In: Fotakis, D., Markakis, E. (eds.) SAGT 2019. LNCS, vol. 11801, pp. 153\u2013167. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-30473-7_11"},{"key":"12_CR9","doi-asserted-by":"publisher","unstructured":"Bertschinger, D., Hertrich, C., Jungeblut, P., Miltzow, T., Weber, S.: Training fully connected neural networks is $$\\exists \\mathbb{R} $$-complete (2022). https:\/\/doi.org\/10.48550\/arXiv.2204.01368","DOI":"10.48550\/arXiv.2204.01368"},{"key":"12_CR10","doi-asserted-by":"publisher","unstructured":"Bil\u00f2, V., Mavronicolas, M.: A catalog of $$\\exists \\mathbb{R} $$-complete problems about Nash equilibria in multi-player games. In: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), pp. 17:1\u201317:13. (LIPIcs) (2016). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2016.17","DOI":"10.4230\/LIPIcs.STACS.2016.17"},{"key":"12_CR11","doi-asserted-by":"publisher","unstructured":"Bil\u00f2, V., Mavronicolas, M.: $$\\exists \\mathbb{R} $$-complete decision problems about symmetric Nash equilibria in symmetric multi-player games. In: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). (LIPIcs), vol. 66, pp. 13:1\u201313:14 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2017.13","DOI":"10.4230\/LIPIcs.STACS.2017.13"},{"issue":"3","key":"12_CR12","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976). https:\/\/doi.org\/10.1016\/S0022-0000(76)80045-1","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"12_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2597629","volume":"61","author":"M \u010cadek","year":"2014","unstructured":"\u010cadek, M., Kr\u010d\u00e1l, M., Matou\u0161ek, J., Sergeraert, F., Vok\u0159\u00ednek, L., Wagner, U.: Computing all maps into a sphere. J. ACM 61(3), 1\u201344 (2014). https:\/\/doi.org\/10.1145\/2597629","journal-title":"J. ACM"},{"issue":"5","key":"12_CR14","doi-asserted-by":"publisher","first-page":"1728","DOI":"10.1137\/120899029","volume":"43","author":"M \u010cadek","year":"2014","unstructured":"\u010cadek, M., Kr\u010d\u00e1l, M., Matou\u0161ek, J., Vok\u0159\u00ednek, L., Wagner, U.: Time computation of homotopy groups and Postnikov systems in fixed dimension. SIAM J. Comput. 43(5), 1728\u20131780 (2014). https:\/\/doi.org\/10.1137\/120899029","journal-title":"SIAM J. Comput."},{"issue":"4","key":"12_CR15","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1007\/s00454-016-9855-6","volume":"57","author":"M \u010cadek","year":"2017","unstructured":"\u010cadek, M., Kr\u010d\u00e1l, M., Vok\u0159\u00ednek, L.: Algorithmic solvability of the lifting-extension problem. Discrete Comput. Geom. (DCG) 57(4), 915\u2013965 (2017). https:\/\/doi.org\/10.1007\/s00454-016-9855-6","journal-title":"Discrete Comput. Geom. (DCG)"},{"issue":"2","key":"12_CR16","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\u2013294 (2018). https:\/\/doi.org\/10.7155\/jgaa.00470","journal-title":"J. Graph Algorithms Appl."},{"key":"12_CR17","doi-asserted-by":"publisher","unstructured":"Chistikov, D., Kiefer, S., Marusic, I., Shirmohammadi, M., Worrell, J.: On restricted nonnegative matrix factorization. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). LIPIcs, vol. 55, pp. 103:1\u2013103:14 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.103","DOI":"10.4230\/LIPIcs.ICALP.2016.103"},{"issue":"4","key":"12_CR18","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/PL00009365","volume":"19","author":"TK Dey","year":"1998","unstructured":"Dey, T.K., Pach, J.: Extremal problems for geometric hypergraphs. Discrete Comput. Geom. 19(4), 473\u2013484 (1998). https:\/\/doi.org\/10.1007\/PL00009365","journal-title":"Discrete Comput. Geom."},{"key":"12_CR19","doi-asserted-by":"publisher","unstructured":"Dobbins, M.G., Holmsen, A., Miltzow, T.: A universality theorem for nested polytopes (2019). https:\/\/doi.org\/10.48550\/arXiv.1908.02213","DOI":"10.48550\/arXiv.1908.02213"},{"key":"12_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-022-00381-0","author":"MG Dobbins","year":"2022","unstructured":"Dobbins, M.G., Kleist, L., Miltzow, T., Rz\u0105\u017cewski, P.: Completeness for the complexity class $$\\forall \\exists \\mathbb{R} $$ and area-universality. Discrete Comput. Geom. (DCG) (2022). https:\/\/doi.org\/10.1007\/s00454-022-00381-0","journal-title":"Discrete Comput. Geom. (DCG)"},{"key":"12_CR21","doi-asserted-by":"publisher","unstructured":"Erickson, J.: Optimal curve straightening is $$\\exists \\mathbb{R} $$-complete (2019). https:\/\/doi.org\/10.48550\/arXiv.1908.09400","DOI":"10.48550\/arXiv.1908.09400"},{"key":"12_CR22","doi-asserted-by":"publisher","unstructured":"Erickson, J., van der Hoog, I., Miltzow, T.: Smoothing the gap between NP and $$\\exists \\mathbb{R} $$. In: IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS 2020), pp. 1022\u20131033 (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00099","DOI":"10.1109\/FOCS46700.2020.00099"},{"key":"12_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-030-35802-0_2","volume-title":"Graph Drawing and Network Visualization","author":"W Evans","year":"2019","unstructured":"Evans, W., Rz\u0105\u017cewski, P., Saeedi, N., Shin, C.-S., Wolff, A.: Representing graphs and hypergraphs by touching polygons in 3D. In: Archambault, D., T\u00f3th, C.D. (eds.) GD 2019. LNCS, vol. 11904, pp. 18\u201332. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-35802-0_2"},{"key":"12_CR24","doi-asserted-by":"publisher","unstructured":"Garg, J., Mehta, R., Vazirani, V.V., Yazdanbod, S.: $$\\exists \\mathbb{R} $$-completeness for decision versions of multi-player (symmetric) Nash equilibria. ACM Trans. Econ. Comput. 6(1), 1:1\u20131:23 (2018). https:\/\/doi.org\/10.1145\/3175494","DOI":"10.1145\/3175494"},{"key":"12_CR25","doi-asserted-by":"publisher","unstructured":"Haussler, D., Welzl, E.: $$\\varepsilon $$-nets and simplex range queries. Discrete & Comput. Geom. 127\u2013151 (1987). https:\/\/doi.org\/10.1007\/BF02187876","DOI":"10.1007\/BF02187876"},{"key":"12_CR26","unstructured":"Hoffmann, M., Miltzow, T., Weber, S., Wulf, L.: Recognition of unit segment graphs is $$\\exists \\mathbb{R} $$-complete, unpublished (2023, in preparation)"},{"key":"12_CR27","doi-asserted-by":"publisher","unstructured":"Jungeblut, P., Kleist, L., Miltzow, T.: The complexity of the Hausdorff distance. In: 38th International Symposium on Computational Geometry (SoCG 2022). LIPIcs, vol. 224, pp. 48:1\u201348:17 (2022). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2022.48","DOI":"10.4230\/LIPIcs.SoCG.2022.48"},{"issue":"3","key":"12_CR28","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). https:\/\/doi.org\/10.1007\/s00454-012-9394-8","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"12_CR29","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"},{"issue":"7","key":"12_CR30","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0898-1221(93)90308-I","volume":"25","author":"PJ Looges","year":"1993","unstructured":"Looges, P.J., Olariu, S.: Optimal greedy algorithms for indifference graphs. Comput. Math. Appl. 25(7), 15\u201325 (1993). https:\/\/doi.org\/10.1016\/0898-1221(93)90308-I","journal-title":"Comput. Math. Appl."},{"key":"12_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/978-3-030-04414-5_28","volume-title":"Graph Drawing and Network Visualization","author":"A Lubiw","year":"2018","unstructured":"Lubiw, A., Miltzow, T., Mondal, D.: The complexity of drawing a graph in a polygonal region. In: Biedl, T., Kerren, A. (eds.) GD 2018. LNCS, vol. 11282, pp. 387\u2013401. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-04414-5_28"},{"key":"12_CR32","unstructured":"Ma, L.: Bisectors and voronoi diagrams for convex distance functions. Ph.D. thesis, FernUniversit\u00e4t Hagen (2000). https:\/\/ub-deposit.fernuni-hagen.de\/receive\/mir_mods_00000857"},{"issue":"1","key":"12_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2582112.2582137","volume":"65","author":"J Matou\u0161ek","year":"2018","unstructured":"Matou\u0161ek, J., Sedgwick, E., Tancer, M., Wagner, U.: Embeddability in the 3-sphere is decidable. J. ACM 65(1), 1\u201349 (2018). https:\/\/doi.org\/10.1145\/2582112.2582137","journal-title":"J. ACM"},{"issue":"2","key":"12_CR34","doi-asserted-by":"publisher","first-page":"259","DOI":"10.4171\/JEMS\/252","volume":"13","author":"J Matou\u0161ek","year":"2011","unstructured":"Matou\u0161ek, J., Tancer, M., Wagner, U.: Hardness of embedding simplicial complexes in $$\\mathbb{R} ^d$$. JEMS 13(2), 259\u2013295 (2011). https:\/\/doi.org\/10.4171\/JEMS\/252","journal-title":"JEMS"},{"key":"12_CR35","doi-asserted-by":"publisher","unstructured":"Matou\u0161ek, J., Seidel, R., Welzl, E.: How to net a lot with little: small $$\\epsilon $$-nets for disks and halfspaces. In: Sixth Annual Symposium on Computational Geometry (SoCG 1990), pp. 16\u201322 (1990). https:\/\/doi.org\/10.1145\/98524.98530","DOI":"10.1145\/98524.98530"},{"issue":"1","key":"12_CR36","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. Combin. Theory Ser. B 103(1), 114\u2013143 (2013). https:\/\/doi.org\/10.1016\/j.jctb.2012.09.004","journal-title":"J. Combin. Theory Ser. B"},{"key":"12_CR37","doi-asserted-by":"publisher","unstructured":"Mesmay, A.D., Rieck, Y., Sedgwick, E., Tancer, M.: Embeddability in $$\\mathbb{R} ^3$$ is NP-hard. J. ACM 67(4), 20:1\u201320:29 (2020). https:\/\/doi.org\/10.1145\/3396593","DOI":"10.1145\/3396593"},{"key":"12_CR38","doi-asserted-by":"publisher","unstructured":"Miltzow, T., Schmiermann, R.F.: On classifying continuous constraint satisfaction problems. In: IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021), pp. 781\u2013791 (2022). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00081","DOI":"10.1109\/FOCS52979.2021.00081"},{"key":"12_CR39","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/BFb0082792","volume-title":"Topology and Geometry\u2014Rohlin Seminar","author":"NE Mnev","year":"1988","unstructured":"Mnev, N.E.: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In: Viro, O.Y., Vershik, A.M. (eds.) Topology and Geometry\u2014Rohlin Seminar. LNM, vol. 1346, pp. 527\u2013543. Springer, Heidelberg (1988). https:\/\/doi.org\/10.1007\/BFb0082792"},{"issue":"3","key":"12_CR40","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1090\/S0894-0347-2012-00759-0","volume":"26","author":"J Pach","year":"2013","unstructured":"Pach, J., Tardos, G.: Tight lower bounds for the size of epsilon-nets. J. Am. Math. Soc. 26(3), 645\u2013658 (2013). https:\/\/doi.org\/10.1090\/S0894-0347-2012-00759-0","journal-title":"J. Am. Math. Soc."},{"key":"12_CR41","doi-asserted-by":"publisher","unstructured":"Pach, J., Woeginger, G.: Some new bounds for epsilon-nets. In: Sixth Annual Symposium on Computational Geometry (SoCG 1990), pp. 10\u201315 (1990). https:\/\/doi.org\/10.1145\/98524.98529","DOI":"10.1145\/98524.98529"},{"issue":"4","key":"12_CR42","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). https:\/\/doi.org\/10.1090\/S0273-0979-1995-00604-X","journal-title":"Bull. Am. Math. Soc."},{"key":"12_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/978-3-642-11805-0_32","volume-title":"Graph Drawing","author":"M Schaefer","year":"2010","unstructured":"Schaefer, M.: Complexity of some geometric and topological problems. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 334\u2013344. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11805-0_32"},{"key":"12_CR44","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/978-1-4614-0110-0_24","volume-title":"Thirty Essays on Geometric Graph Theory","author":"M Schaefer","year":"2013","unstructured":"Schaefer, M.: Realizability of graphs and linkages. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 461\u2013482. Springer, New York (2013). https:\/\/doi.org\/10.1007\/978-1-4614-0110-0_24"},{"issue":"1","key":"12_CR45","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."},{"issue":"2","key":"12_CR46","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0022-0000(03)00045-X","volume":"67","author":"M Schaefer","year":"2003","unstructured":"Schaefer, M., Sedgwick, E., \u0160tefankovi\u010d, D.: Recognizing string graphs in NP. J. Comput. Syst. Sci. 67(2), 365\u2013380 (2003). https:\/\/doi.org\/10.1016\/S0022-0000(03)00045-X","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR47","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, 172\u2013193 (2017). https:\/\/doi.org\/10.1007\/s00224-015-9662-0","journal-title":"Theory Comput. Syst."},{"issue":"5","key":"12_CR48","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":"12_CR49","doi-asserted-by":"publisher","unstructured":"Shitov, Y.: A universality theorem for nonnegative matrix factorizations (2016). https:\/\/doi.org\/10.48550\/arXiv.1606.09068","DOI":"10.48550\/arXiv.1606.09068"},{"issue":"3","key":"12_CR50","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":"12_CR51","doi-asserted-by":"publisher","unstructured":"Shor, P.W.: Stretchability of pseudolines is NP-hard. In: Gritzmann, P., Sturmfels, B. (eds.) Applied Geometry And Discrete Mathematics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 4, pp. 531\u2013554 (1991). https:\/\/doi.org\/10.1090\/dimacs\/004\/41","DOI":"10.1090\/dimacs\/004\/41"},{"key":"12_CR52","doi-asserted-by":"publisher","unstructured":"Skopenkov, A.: Extendability of simplicial maps is undecidable (2020). https:\/\/doi.org\/10.48550\/arXiv.2008.00492","DOI":"10.48550\/arXiv.2008.00492"},{"issue":"3","key":"12_CR53","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/050642368","volume":"21","author":"S Smorodinsky","year":"2007","unstructured":"Smorodinsky, S.: On the chromatic number of geometric hypergraphs. SIAM J. Discrete Math. 21(3), 676\u2013687 (2007). https:\/\/doi.org\/10.1137\/050642368","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"12_CR54","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1006\/jagm.1994.1012","volume":"16","author":"J Spinrad","year":"1994","unstructured":"Spinrad, J.: Recognition of circle graphs. J. Algorithms 16(2), 264\u2013282 (1994). https:\/\/doi.org\/10.1006\/jagm.1994.1012","journal-title":"J. Algorithms"},{"key":"12_CR55","doi-asserted-by":"publisher","unstructured":"Stade, J.: Complexity of the boundary-guarding art gallery problem (2022). https:\/\/doi.org\/10.48550\/arXiv.2210.12817","DOI":"10.48550\/arXiv.2210.12817"},{"key":"12_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/3-540-58950-3_375","volume-title":"Graph Drawing","author":"PJ Tanenbaum","year":"1995","unstructured":"Tanenbaum, P.J., Goodrich, M.T., Scheinerman, E.R.: Characterization and recognition of point-halfspace and related orders. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 234\u2013245. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-58950-3_375"},{"key":"12_CR57","doi-asserted-by":"publisher","unstructured":"Tuncel, L., Vavasis, S., Xu, J.: Computational complexity of decomposing a symmetric matrix as a sum of positive semidefinite and diagonal matrices (2022). https:\/\/doi.org\/10.48550\/arXiv.2209.05678","DOI":"10.48550\/arXiv.2209.05678"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing and Network Visualization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-49272-3_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,11]],"date-time":"2024-01-11T09:06:30Z","timestamp":1704963990000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-49272-3_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031492716","9783031492723"],"references-count":57,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-49272-3_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"1 January 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"GD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Graph Drawing and Network Visualization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Isola delle Femmine, Palermo","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"gd2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/gd2023.ing.unipg.it\/\/","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":"100","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":"31","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":"7","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":"31% - 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","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":"13","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","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)"}},{"value":"11 posters, 2 abstracts of invited talks, and 1 contest report are also included in the GD 2023 proceedings","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}