{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T12:34:55Z","timestamp":1768394095007,"version":"3.49.0"},"reference-count":65,"publisher":"MathDoc\/Centre Mersenne","license":[{"start":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T00:00:00Z","timestamp":1745452800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"\n As set systems, hypergraphs are omnipresent and have various representations ranging from Euler and Venn diagrams to contact representations. In a\n geometric representation<\/jats:italic>\n of a hypergraph\n \n \n H<\/mml:mi>\n =<\/mml:mo>\n (<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n , each vertex\n \n \n v<\/mml:mi>\n \u2208<\/mml:mo>\n V<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n is associated with a point\n \n \n \n p<\/mml:mi>\n v<\/mml:mi>\n <\/mml:msub>\n \u2208<\/mml:mo>\n \n \u211d<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n and each hyperedge\n \n \n e<\/mml:mi>\n \u2208<\/mml:mo>\n E<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n is associated with a connected set\n \n \n \n s<\/mml:mi>\n e<\/mml:mi>\n <\/mml:msub>\n \u2282<\/mml:mo>\n \n \u211d<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n such that\n \n \n \n {<\/mml:mo>\n \n p<\/mml:mi>\n v<\/mml:mi>\n <\/mml:msub>\n \u2223<\/mml:mo>\n v<\/mml:mi>\n \u2208<\/mml:mo>\n V<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n \u2229<\/mml:mo>\n \n s<\/mml:mi>\n e<\/mml:mi>\n <\/mml:msub>\n =<\/mml:mo>\n \n {<\/mml:mo>\n \n p<\/mml:mi>\n v<\/mml:mi>\n <\/mml:msub>\n \u2223<\/mml:mo>\n v<\/mml:mi>\n \u2208<\/mml:mo>\n e<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n for all\n \n \n e<\/mml:mi>\n \u2208<\/mml:mo>\n E<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n . We say that a given hypergraph\n \n H<\/mml:mi>\n <\/mml:math>\n is\n representable<\/jats:italic>\n by some (infinite) family\n \n \u2131<\/mml:mi>\n <\/mml:math>\n of sets in\n \n \n \u211d<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n , if there exist\n \n \n P<\/mml:mi>\n \u2282<\/mml:mo>\n \n \u211d<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n and\n \n \n S<\/mml:mi>\n \u2286<\/mml:mo>\n \u2131<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n such that\n \n \n (<\/mml:mo>\n P<\/mml:mi>\n ,<\/mml:mo>\n S<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n is a geometric representation of\u00a0\n \n H<\/mml:mi>\n <\/mml:math>\n . For a family\n \n \u2131<\/mml:mi>\n <\/mml:math>\n , we define\n Recognition<\/jats:sc>\n (\n \n \u2131<\/mml:mi>\n <\/mml:math>\n ) as the problem to determine if a given hypergraph is representable by\n \n \u2131<\/mml:mi>\n <\/mml:math>\n . It is known that the\n Recognition<\/jats:sc>\n problem is\n \n \n \u2203<\/mml:mo>\n \u211d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n -hard for halfspaces in\n \n \n \u211d<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n . We study the families of translates and homothets of balls and ellipsoids in\n \n \n \u211d<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n , as well as of other convex sets, and show that their\n Recognition<\/jats:sc>\n problems are also\n \n \n \u2203<\/mml:mo>\n \u211d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n -complete. In particular, for a\n bi-curved, computable<\/jats:italic>\n set\n \n C<\/mml:mi>\n <\/mml:math>\n , the recognition problem of the family of translates (or homothets) of\n \n C<\/mml:mi>\n <\/mml:math>\n is\n \n \n \u2203<\/mml:mo>\n \u211d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n -complete if it is\n T-difference-separable (H-difference-separable)<\/jats:italic>\n . We show that for bounded sets in the plane, convexity is equivalent to T-difference-separability and H-difference-separability; in higher dimensions, convexity is necessary but not sufficient. Our results imply that these recognition problems are equivalent to deciding whether a multivariate system of polynomial equations with integer coefficients has a real solution.\n <\/jats:p>","DOI":"10.5802\/igt.9","type":"journal-article","created":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T10:49:20Z","timestamp":1745491760000},"page":"157-190","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Recognizing Geometric Hypergraphs"],"prefix":"10.5802","volume":"2","author":[{"given":"Daniel","family":"Bertschinger","sequence":"first","affiliation":[{"name":"ETH Z\u00fcrich, Department of Computer Science, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"El\u00a0Maalouly","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Department of Computer Science, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Linda","family":"Kleist","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Potsdam, Institute of Computer Science, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tillmann","family":"Miltzow","sequence":"additional","affiliation":[{"name":"Utrecht University, Department of Information and Computing Sciences, the Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simon","family":"Weber","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Department of Computer Science, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"3842","published-online":{"date-parts":[[2025,4,24]]},"reference":[{"key":"key2025121216553190395_1","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1109\/FOCS52979.2021.00045","article-title":"Covering Polygons is Even Harder","author":"Abrahamsen, Mikkel","year":"2022","unstructured":"[1] Abrahamsen, Mikkel Covering Polygons is Even Harder, IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS 2022) (2022), pp. 375-386","journal-title":"IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS 2022)"},{"key":"key2025121216553190395_2","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1145\/3188745.3188868","article-title":"The Art Gallery Problem is \u2203<\/mo>\u211d<\/mi><\/mrow><\/math><\/span>-complete","author":"Abrahamsen, Mikkel","year":"2018","unstructured":"[2] Abrahamsen, Mikkel; Adamaszek, Anna; Miltzow, Tillmann The Art Gallery Problem is \u2203\u211d-complete, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018) (2018), pp. 65-73","journal-title":"Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018)"},{"key":"key2025121216553190395_3","first-page":"18293","article-title":"Training Neural Networks is \u2203<\/mo>\u211d<\/mi><\/mrow><\/math><\/span>-complete","author":"Abrahamsen, Mikkel","year":"2021","unstructured":"[3] Abrahamsen, Mikkel; Kleist, Linda; Miltzow, Tillmann Training Neural Networks is \u2203\u211d-complete, Advances in Neural Information Processing Systems (NeurIPS 2021) (2021), pp. 18293-18306 https:\/\/proceedings.neurips.cc\/...","journal-title":"Advances in Neural Information Processing Systems (NeurIPS 2021)"},{"key":"key2025121216553190395_4","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2108.02585","author":"Abrahamsen, Mikkel","year":"2023","unstructured":"[4] Abrahamsen, Mikkel; Kleist, Linda; Miltzow, Tillmann Geometric Embeddability of Complexes is \u2203\u211d-complete (2023) To appear in: Symposium on Computational Geometry (SOCG 2023)","journal-title":"Geometric Embeddability of Complexes is \u2203<\/mo>\u211d<\/mi><\/mrow><\/math><\/span>-complete"},{"key":"key2025121216553190395_5","doi-asserted-by":"publisher","first-page":"1014","DOI":"10.1109\/FOCS46700.2020.00098","article-title":"Framework for \u2203<\/mo>\u211d<\/mi><\/mrow><\/math><\/span>-Completeness of Two-Dimensional Packing Problems","author":"Abrahamsen, Mikkel","year":"2020","unstructured":"[5] Abrahamsen, Mikkel; Miltzow, Tillmann; Seiferth, Nadja Framework for \u2203\u211d-Completeness of Two-Dimensional Packing Problems, IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS 2020) (2020), pp. 1014-1021","journal-title":"IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS 2020)"},{"issue":"7","key":"key2025121216553190395_6","doi-asserted-by":"publisher","first-page":"3248","DOI":"10.1137\/090762968","article-title":"Small-Size \u03f5<\/mi><\/math><\/span>-Nets for Axis-Parallel Rectangles and Boxes","volume":"39","author":"Aronov, Boris","year":"2010","unstructured":"[6] Aronov, Boris; Ezra, Esther; Sharir, Micha Small-Size \u03f5-Nets for Axis-Parallel Rectangles and Boxes, SIAM Journal on Computing (SiComp), Volume 39 (2010) no. 7, pp. 3248-3282","journal-title":"SIAM Journal on Computing (SiComp)"},{"issue":"1","key":"key2025121216553190395_7","doi-asserted-by":"publisher","DOI":"10.20382\/jocg.v7i1a1","article-title":"Density of range capturing hypergraphs","volume":"7","author":"Axenovich, Maria","year":"2016","unstructured":"[7] Axenovich, Maria; Ueckerdt, Torsten Density of range capturing hypergraphs, Journal of Computational Geometry (JoCG), Volume 7 (2016) no. 1","journal-title":"Journal of Computational Geometry (JoCG)"},{"key":"key2025121216553190395_8","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-030-30473-7_11","article-title":"On the Computational Complexity of Problems About Multi-player Nash Equilibria","volume":"11801","author":"Berthelsen, Marie L. T.","year":"2019","unstructured":"[8] Berthelsen, Marie L. T.; Hansen, Kristoffer A. On the Computational Complexity of Problems About Multi-player Nash Equilibria, International Symposium on Algorithmic Game Theory (LNCS), Volume 11801 (2019), pp. 153-167","journal-title":"International Symposium on Algorithmic Game Theory"},{"key":"key2025121216553190395_9","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-031-49272-3_12","article-title":"The Complexity of Recognizing Geometric Hypergraphs","author":"Bertschinger, Daniel","year":"2023","unstructured":"[9] Bertschinger, Daniel; El Maalouly, Nicolas; Kleist, Linda; Miltzow, Tillmann; Weber, Simon The Complexity of Recognizing Geometric Hypergraphs, Graph Drawing and Network Visualization (GD\u201923) (2023), pp. 163-179","journal-title":"Graph Drawing and Network Visualization (GD\u201923)"},{"key":"key2025121216553190395_10","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2204.01368","author":"Bertschinger, Daniel","year":"2022","unstructured":"[10] Bertschinger, Daniel; Hertrich, Christoph; Jungeblut, Paul; Miltzow, Tillmann; Weber, Simon Training Fully Connected Neural Networks is \u2203\u211d-Complete (2022)","journal-title":"Training Fully Connected Neural Networks is \u2203<\/mo>\u211d<\/mi><\/mrow><\/math><\/span>-Complete"},{"key":"key2025121216553190395_11","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.4230\/LIPIcs.STACS.2016.17","article-title":"A Catalog of \u2203<\/mo>\u211d<\/mi><\/mrow><\/math><\/span>-Complete Problems About Nash Equilibria in Multi-Player Games","author":"Bil\u00f2, Vittorio","year":"2016","unstructured":"[11] Bil\u00f2, Vittorio; Mavronicolas, Marios A Catalog of \u2203\u211d-Complete Problems About Nash Equilibria in Multi-Player Games, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) ((LIPIcs)) (2016), p. 17:1-17:13","journal-title":"33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)"},{"key":"key2025121216553190395_12","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.4230\/LIPIcs.STACS.2017.13","article-title":"\u2203<\/mo>\u211d<\/mi><\/mrow><\/math><\/span>-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games","volume":"66","author":"Bil\u00f2, Vittorio","year":"2017","unstructured":"[12] Bil\u00f2, Vittorio; Mavronicolas, Marios \u2203\u211d-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) ((LIPIcs)), Volume 66 (2017), p. 13:1-13:14","journal-title":"34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)"},{"issue":"3","key":"key2025121216553190395_13","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","article-title":"Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms","volume":"13","author":"Booth, Kellogg S.","year":"1976","unstructured":"[13] Booth, Kellogg S.; Lueker, George S. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Journal of Computer and System Sciences, Volume 13 (1976) no. 3, pp. 335-379","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"key2025121216553190395_14","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","article-title":"Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms","volume":"13","author":"Booth, Kellogg S.","year":"1976","unstructured":"[14] Booth, Kellogg S.; Lueker, George S. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Journal of computer and system sciences, Volume 13 (1976) no. 3, pp. 335-379","journal-title":"Journal of computer and system sciences"},{"issue":"3","key":"key2025121216553190395_15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2597629","article-title":"Computing all maps into a sphere","volume":"61","author":"\u010cadek, Martin","year":"2014","unstructured":"[15] \u010cadek, Martin; Kr\u010d\u00e1l, Marek; Matou\u0161ek, Ji\u0159\u00ed; Sergeraert, Francis; Vok\u0159\u00ednek, Luk\u00e1\u0161; Wagner, Uli Computing all maps into a sphere, Journal of the ACM, Volume 61 (2014) no. 3, pp. 1-44","journal-title":"Journal of the ACM"},{"issue":"5","key":"key2025121216553190395_16","doi-asserted-by":"publisher","first-page":"1728","DOI":"10.1137\/120899029","article-title":"Time computation of homotopy groups and Postnikov systems in fixed dimension","volume":"43","author":"\u010cadek, Martin","year":"2014","unstructured":"[16] \u010cadek, Martin; Kr\u010d\u00e1l, Marek; Matou\u0161ek, Ji\u0159\u00ed; Vok\u0159\u00ednek, Luk\u00e1\u0161; Wagner, Uli Time computation of homotopy groups and Postnikov systems in fixed dimension, SIAM Journal on Computing, Volume 43 (2014) no. 5, pp. 1728-1780","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"key2025121216553190395_17","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1007\/s00454-016-9855-6","article-title":"Algorithmic solvability of the lifting-extension problem","volume":"57","author":"\u010cadek, Martin","year":"2017","unstructured":"[17] \u010cadek, Martin; Kr\u010d\u00e1l, Marek; Vok\u0159\u00ednek, Luk\u00e1\u0161 Algorithmic solvability of the lifting-extension problem, Discrete & Computational Geometry (DCG), Volume 57 (2017) no. 4, pp. 915-965","journal-title":"Discrete & Computational Geometry (DCG)"},{"issue":"2","key":"key2025121216553190395_18","doi-asserted-by":"publisher","first-page":"273","DOI":"10.7155\/jgaa.00470","article-title":"Intersection Graphs of Rays and Grounded Segments","volume":"22","author":"Cardinal, Jean","year":"2018","unstructured":"[18] Cardinal, Jean; Felsner, Stefan; Miltzow, Tillmann; Tompkins, Casey; Vogtenhuber, Birgit Intersection Graphs of Rays and Grounded Segments, Journal of Graph Algorithms and Applications, Volume 22 (2018) no. 2, pp. 273-294","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"key2025121216553190395_19","doi-asserted-by":"publisher","first-page":"103:1","DOI":"10.4230\/LIPIcs.ICALP.2016.103","article-title":"On Restricted Nonnegative Matrix Factorization","volume":"55","author":"Chistikov, Dmitry","year":"2016","unstructured":"[19] Chistikov, Dmitry; Kiefer, Stefan; Marusic, Ines; Shirmohammadi, Mahsa; Worrell, James On Restricted Nonnegative Matrix Factorization, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) (LIPIcs), Volume 55 (2016), p. 103:1-103:14","journal-title":"43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)"},{"issue":"4","key":"key2025121216553190395_20","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/PL00009365","article-title":"Extremal Problems for Geometric Hypergraphs","volume":"19","author":"Dey, T. K.","year":"1998","unstructured":"[20] Dey, T. K.; Pach, J\u00e1nos Extremal Problems for Geometric Hypergraphs, Discrete & Computational Geometry, Volume 19 (1998) no. 4, pp. 473-484","journal-title":"Discrete & Computational Geometry"},{"key":"key2025121216553190395_21","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1908.02213","author":"Dobbins, Michael G.","year":"2019","unstructured":"[21] Dobbins, Michael G.; Holmsen, Andreas; Miltzow, Tillmann A Universality Theorem for Nested Polytopes (2019)","journal-title":"A Universality Theorem for Nested Polytopes"},{"issue":"1","key":"key2025121216553190395_22","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/s00454-022-00381-0","article-title":"Completeness for the Complexity Class \u2200<\/mo>\u2203<\/mo>\u211d<\/mi><\/mrow><\/math><\/span> and Area-Universality","volume":"70","author":"Dobbins, Michael G.","year":"2022","unstructured":"[22] Dobbins, Michael G.; Kleist, Linda; Miltzow, Tillmann; Rz\u0105\u017cewski, Pawe\u0142 Completeness for the Complexity Class \u2200\u2203\u211d and Area-Universality, Discrete & Computational Geometry (DCG), Volume 70 (2022) no. 1, pp. 154-188","journal-title":"Discrete & Computational Geometry (DCG)"},{"key":"key2025121216553190395_23","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1908.09400","author":"Erickson, Jeff","year":"2019","unstructured":"[23] Erickson, Jeff Optimal Curve Straightening is \u2203\u211d-Complete (2019)","journal-title":"Optimal Curve Straightening is \u2203<\/mo>\u211d<\/mi><\/mrow><\/math><\/span>-Complete"},{"key":"key2025121216553190395_24","doi-asserted-by":"publisher","first-page":"1022","DOI":"10.1109\/FOCS46700.2020.00099","article-title":"Smoothing the gap between NP and \u2203<\/mo>\u211d<\/mi><\/mrow><\/math><\/span>","author":"Erickson, Jeff","year":"2020","unstructured":"[24] Erickson, Jeff; van der Hoog, Ivor; Miltzow, Tillmann Smoothing the gap between NP and \u2203\u211d, IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS 2020) (2020), pp. 1022-1033","journal-title":"IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS 2020)"},{"key":"key2025121216553190395_25","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-030-35802-0_2","article-title":"Representing Graphs and Hypergraphs by Touching Polygons in 3D,","author":"Evans, William","year":"2019","unstructured":"[25] Evans, William; Rz\u0105\u017cewski, Pawe\u0142; Saeedi, Noushin; Shin, Chan-Su; Wolff, Alexander Representing Graphs and Hypergraphs by Touching Polygons in 3D,, Graph Drawing and Network Visualization (GD 2019) (2019), pp. 18-32","journal-title":"Graph Drawing and Network Visualization (GD 2019)"},{"issue":"22","key":"key2025121216553190395_26","doi-asserted-by":"publisher","first-page":"2906","DOI":"10.1016\/j.disc.2006.04.043","article-title":"The Roberts characterization of proper and unit interval graphs","volume":"307","author":"Gardi, Fr\u00e9d\u00e9ric","year":"2007","unstructured":"[26] Gardi, Fr\u00e9d\u00e9ric The Roberts characterization of proper and unit interval graphs, Discrete Mathematics, Volume 307 (2007) no. 22, pp. 2906-2908","journal-title":"Discrete Mathematics"},{"issue":"1","key":"key2025121216553190395_27","doi-asserted-by":"publisher","DOI":"10.1145\/3175494","article-title":"\u2203<\/mo>\u211d<\/mi><\/mrow><\/math><\/span>-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria","volume":"6","author":"Garg, Jugal","year":"2018","unstructured":"[27] Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.; Yazdanbod, Sadra \u2203\u211d-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria, ACM Transactions on Economics and Computation, Volume 6 (2018) no. 1, 1, 23 pages","journal-title":"ACM Transactions on Economics and Computation"},{"issue":"1","key":"key2025121216553190395_28","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/s0304-3975(97)00241-7","article-title":"Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing","volume":"234","author":"Habib, Michel","year":"2000","unstructured":"[28] Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoretical Computer Science, Volume 234 (2000) no. 1, pp. 59-84","journal-title":"Theoretical Computer Science"},{"key":"key2025121216553190395_29","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","article-title":"\u03b5<\/mi><\/math><\/span>-nets and simplex range queries","author":"Haussler, David","year":"1987","unstructured":"[29] Haussler, David; Welzl, Emo \u03b5-nets and simplex range queries, Discrete & Computational Geometry (1987), pp. 127-151","journal-title":"Discrete & Computational Geometry"},{"key":"key2025121216553190395_30","author":"Hoffmann, Michael","unstructured":"[30] Hoffmann, Michael; Miltzow, Tillmann; Weber, Simon; Wulf, Lasse Recognition of Unit Segment Graphs is \u2203\u211d-complete (Unpublished, in preparation.)","journal-title":"Recognition of Unit Segment Graphs is \u2203<\/mo>\u211d<\/mi><\/mrow><\/math><\/span>-complete"},{"key":"key2025121216553190395_31","doi-asserted-by":"publisher","first-page":"48:1","DOI":"10.4230\/LIPIcs.SoCG.2022.48","article-title":"The Complexity of the Hausdorff Distance","volume":"224","author":"Jungeblut, Paul","year":"2022","unstructured":"[31] Jungeblut, Paul; Kleist, Linda; Miltzow, Tillmann The Complexity of the Hausdorff Distance, 38th International Symposium on Computational Geometry (SoCG 2022) (LIPIcs), Volume 224 (2022), p. 48:1-48:17","journal-title":"38th International Symposium on Computational Geometry (SoCG 2022)"},{"key":"key2025121216553190395_32","first-page":"218","article-title":"On some properties of convex curves and surfaces","volume":"8","author":"Kakeya, S\u00f4ichi","year":"1915","unstructured":"[32] Kakeya, S\u00f4ichi On some properties of convex curves and surfaces, Tohoku Mathematical Journal, First Series, Volume 8 (1915), pp. 218-221 https:\/\/www.jstage.jst.go.jp\/...","journal-title":"Tohoku Mathematical Journal, First Series"},{"issue":"3","key":"key2025121216553190395_33","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1007\/s00454-012-9394-8","article-title":"Sphere and Dot Product Representations of Graphs","volume":"47","author":"Kang, Ross J.","year":"2012","unstructured":"[33] Kang, Ross J.; M\u00fcller, Tobias Sphere and Dot Product Representations of Graphs, Discrete & Computational Geometry, Volume 47 (2012) no. 3, pp. 548-568","journal-title":"Discrete & Computational Geometry"},{"issue":"2","key":"key2025121216553190395_34","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1006\/jctb.1994.1071","article-title":"Intersection Graphs of Segments","volume":"62","author":"Kratochv\u00edl, Jan","year":"1994","unstructured":"[34] Kratochv\u00edl, Jan; Matou\u0161ek, Ji\u0159\u00ed Intersection Graphs of Segments, Journal of Combinatorial Theory, Series B, Volume 62 (1994) no. 2, pp. 289-315","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"7","key":"key2025121216553190395_35","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0898-1221(93)90308-I","article-title":"Optimal greedy algorithms for indifference graphs","volume":"25","author":"Looges, Peter J.","year":"1993","unstructured":"[35] Looges, Peter J.; Olariu, Stephan Optimal greedy algorithms for indifference graphs, Computers & Mathematics with Applications, Volume 25 (1993) no. 7, pp. 15-25","journal-title":"Computers & Mathematics with Applications"},{"key":"key2025121216553190395_36","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/978-3-030-04414-5_28","article-title":"The Complexity of Drawing a Graph in a Polygonal Region","volume":"11282","author":"Lubiw, Anna","year":"2018","unstructured":"[36] Lubiw, Anna; Miltzow, Tillmann; Mondal, Debajyoti The Complexity of Drawing a Graph in a Polygonal Region, Graph Drawing and Network Visualization (GD 2018) (LNCS), Volume 11282 (2018), pp. 387-401","journal-title":"Graph Drawing and Network Visualization (GD 2018)"},{"key":"key2025121216553190395_37","author":"Ma, Lihong","year":"2000","unstructured":"[37] Ma, Lihong Bisectors and Voronoi Diagrams for Convex Distance Functions, Ph. D. Thesis, FernUniversit\u00e4t Hagen (2000) https:\/\/ub-deposit.fernuni-hagen.de\/...","journal-title":"Bisectors and Voronoi Diagrams for Convex Distance Functions"},{"issue":"1","key":"key2025121216553190395_38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2582112.2582137","article-title":"Embeddability in the 3-sphere is decidable","volume":"65","author":"Matou\u0161ek, Ji\u0159\u00ed","year":"2018","unstructured":"[38] Matou\u0161ek, Ji\u0159\u00ed; Sedgwick, Eric; Tancer, Martin; Wagner, Uli Embeddability in the 3-sphere is decidable, Journal of the ACM, Volume 65 (2018) no. 1, pp. 1-49","journal-title":"Journal of the ACM"},{"key":"key2025121216553190395_39","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/98524.98530","article-title":"How to Net a Lot with Little: Small \u03f5<\/mi><\/math><\/span>-Nets for Disks and Halfspaces","author":"Matou\u0161ek, Ji\u0159\u00ed","year":"1990","unstructured":"[39] Matou\u0161ek, Ji\u0159\u00ed; Seidel, Raimund; Welzl, Emo How to Net a Lot with Little: Small \u03f5-Nets for Disks and Halfspaces, Sixth Annual Symposium on Computational Geometry (SoCG 1990) (1990), pp. 16-22","journal-title":"Sixth Annual Symposium on Computational Geometry (SoCG 1990)"},{"issue":"2","key":"key2025121216553190395_40","doi-asserted-by":"publisher","first-page":"259","DOI":"10.4171\/JEMS\/252","article-title":"Hardness of embedding simplicial complexes in \u211d<\/mi> d<\/mi> <\/msup><\/math><\/span>","volume":"13","author":"Matou\u0161ek, Ji\u0159\u00ed","year":"2011","unstructured":"[40] Matou\u0161ek, Ji\u0159\u00ed; Tancer, Martin; Wagner, Uli Hardness of embedding simplicial complexes in \u211d d , JEMS, Volume 13 (2011) no. 2, pp. 259-295","journal-title":"JEMS"},{"issue":"1","key":"key2025121216553190395_41","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.jctb.2012.09.004","article-title":"Integer realizations of disk and segment graphs","volume":"103","author":"McDiarmid, Colin","year":"2013","unstructured":"[41] McDiarmid, Colin; M\u00fcller, Tobias Integer realizations of disk and segment graphs, Journal of Combinatorial Theory, Series B, Volume 103 (2013) no. 1, pp. 114-143","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"4","key":"key2025121216553190395_42","doi-asserted-by":"publisher","DOI":"10.1145\/3396593","article-title":"Embeddability in \u211d<\/mi> 3<\/mn> <\/msup><\/math><\/span> is NP-hard","volume":"67","author":"Mesmay, Arnaud de","year":"2020","unstructured":"[42] Mesmay, Arnaud de; Rieck, Yo\u2019av; Sedgwick, Eric; Tancer, Martin Embeddability in \u211d 3 is NP-hard, Journal of the ACM, Volume 67 (2020) no. 4, 20, 29 pages","journal-title":"Journal of the ACM"},{"key":"key2025121216553190395_43","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1109\/FOCS52979.2021.00081","article-title":"On Classifying Continuous Constraint Satisfaction Problems","author":"Miltzow, Tillmann","year":"2022","unstructured":"[43] Miltzow, Tillmann; Schmiermann, Reinier F. On Classifying Continuous Constraint Satisfaction Problems, IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021) (2022), pp. 781-791","journal-title":"IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021)"},{"key":"key2025121216553190395_44","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/BFb0082792","article-title":"The Universality Theorems on the Classification Problem of Configuration Varieties and Convex Polytopes Varieties","volume":"1346","author":"Mn\u00ebv, Nikolai E.","year":"1988","unstructured":"[44] Mn\u00ebv, Nikolai E. The Universality Theorems on the Classification Problem of Configuration Varieties and Convex Polytopes Varieties, Topology and Geometry \u2014 Rohlin Seminar (LNM), Volume 1346, Springer, 1988, pp. 527-543","journal-title":"Topology and Geometry \u2014 Rohlin Seminar"},{"key":"key2025121216553190395_45","first-page":"11","article-title":"On some theorems regarding ellipsoid","volume":"8","author":"Nakagawa, Senkichi","year":"1915","unstructured":"[45] Nakagawa, Senkichi On some theorems regarding ellipsoid, Tohoku Mathematical Journal, First Series, Volume 8 (1915), pp. 11-13 https:\/\/www.jstage.jst.go.jp\/...","journal-title":"Tohoku Mathematical Journal, First Series"},{"issue":"3","key":"key2025121216553190395_46","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1090\/S0894-0347-2012-00759-0","article-title":"TIGHT LOWER BOUNDS FOR THE SIZE OF EPSILON-NETS","volume":"26","author":"Pach, J\u00e1nos","year":"2013","unstructured":"[46] Pach, J\u00e1nos; Tardos, G\u00e1bor TIGHT LOWER BOUNDS FOR THE SIZE OF EPSILON-NETS, Journal of the American Mathematical Society, Volume 26 (2013) no. 3, pp. 645-658","journal-title":"Journal of the American Mathematical Society"},{"key":"key2025121216553190395_47","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/98524.98529","article-title":"Some New Bounds for Epsilon-Nets","author":"Pach, J\u00e1nos","year":"1990","unstructured":"[47] Pach, J\u00e1nos; Woeginger, Gerhard Some New Bounds for Epsilon-Nets, Sixth Annual Symposium on Computational Geometry (SoCG 1990) (1990), pp. 10-15","journal-title":"Sixth Annual Symposium on Computational Geometry (SoCG 1990)"},{"issue":"10-11","key":"key2025121216553190395_48","doi-asserted-by":"publisher","first-page":"1601","DOI":"10.1016\/j.dam.2012.02.014","article-title":"Unit and single point interval graphs","volume":"160","author":"Rautenbach, Dieter","year":"2012","unstructured":"[48] Rautenbach, Dieter; Szwarcfiter, Jayme L. Unit and single point interval graphs, Discrete Applied Mathematics, Volume 160 (2012) no. 10-11, pp. 1601-1609","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"key2025121216553190395_49","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1090\/S0273-0979-1995-00604-X","article-title":"Realization Spaces of 4-Polytopes are Universal","volume":"32","author":"Richter-Gebert, J\u00fcrgen","year":"1995","unstructured":"[49] Richter-Gebert, J\u00fcrgen; Ziegler, G\u00fcnter M. Realization Spaces of 4-Polytopes are Universal, Bulletin of the American Mathematical Society, Volume 32 (1995) no. 4, pp. 403-412","journal-title":"Bulletin of the American Mathematical Society"},{"key":"key2025121216553190395_50","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/978-3-642-11805-0","article-title":"Complexity of Some Geometric and Topological Problems","author":"Schaefer, Marcus","year":"2010","unstructured":"[50] Schaefer, Marcus Complexity of Some Geometric and Topological Problems, Graph Drawing, Springer (2010), pp. 334-344","journal-title":"Graph Drawing"},{"key":"key2025121216553190395_51","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/978-1-4614-0110-0_24","author":"Schaefer, Marcus","year":"2013","unstructured":"[51] Schaefer, Marcus Realizability of Graphs and Linkages, Thirty Essays on Geometric Graph Theory, Springer (2013), pp. 461-482","journal-title":"Realizability of Graphs and Linkages"},{"issue":"1","key":"key2025121216553190395_52","doi-asserted-by":"publisher","first-page":"29","DOI":"10.7155\/jgaa.00548","article-title":"Complexity of Geometric k-Planarity for Fixed k","volume":"25","author":"Schaefer, Marcus","year":"2021","unstructured":"[52] Schaefer, Marcus Complexity of Geometric k-Planarity for Fixed k, Journal of Graph Algorithms and Applications, Volume 25 (2021) no. 1, pp. 29-41","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"key2025121216553190395_53","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2407.18006","author":"Schaefer, Marcus","year":"2024","unstructured":"[53] Schaefer, Marcus; Cardinal, Jean; Miltzow, Tillmann The existential theory of the reals as a complexity class: A compendium (2024)","journal-title":"The existential theory of the reals as a complexity class: A compendium"},{"issue":"2","key":"key2025121216553190395_54","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0022-0000(03)00045-X","article-title":"Recognizing string graphs in NP","volume":"67","author":"Schaefer, Marcus","year":"2003","unstructured":"[54] Schaefer, Marcus; Sedgwick, Eric; \u0160tefankovi\u010d, Daniel Recognizing string graphs in NP, Journal of Computer and System Sciences, Volume 67 (2003) no. 2, pp. 365-380","journal-title":"Journal of Computer and System Sciences"},{"key":"key2025121216553190395_55","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/s00224-015-9662-0","article-title":"Fixed Points, Nash Equilibria, and the Existential Theory of the Reals","volume":"60","author":"Schaefer, Marcus","year":"2017","unstructured":"[55] Schaefer, Marcus; \u0160tefankovi\u010d, Daniel Fixed Points, Nash Equilibria, and the Existential Theory of the Reals, Theory of Computing Systems, Volume 60 (2017), pp. 172-193","journal-title":"Theory of Computing Systems"},{"issue":"5","key":"key2025121216553190395_56","doi-asserted-by":"publisher","first-page":"1161","DOI":"10.1007\/s00224-017-9800-y","article-title":"The Complexity of Tensor Rank","volume":"62","author":"Schaefer, Marcus","year":"2018","unstructured":"[56] Schaefer, Marcus; \u0160tefankovi\u010d, Daniel The Complexity of Tensor Rank, Theory of Computing Systems, Volume 62 (2018) no. 5, pp. 1161-1174","journal-title":"Theory of Computing Systems"},{"key":"key2025121216553190395_57","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1606.09068","author":"Shitov, Yaroslav","year":"2016","unstructured":"[57] Shitov, Yaroslav A Universality Theorem for Nonnegative Matrix Factorizations (2016)","journal-title":"A Universality Theorem for Nonnegative Matrix Factorizations"},{"issue":"3","key":"key2025121216553190395_58","doi-asserted-by":"publisher","first-page":"1898","DOI":"10.1137\/16M1080616","article-title":"The Complexity of Positive Semidefinite Matrix Factorization","volume":"27","author":"Shitov, Yaroslav","year":"2017","unstructured":"[58] Shitov, Yaroslav The Complexity of Positive Semidefinite Matrix Factorization, SIAM Journal on Optimization, Volume 27 (2017) no. 3, pp. 1898-1909","journal-title":"SIAM Journal on Optimization"},{"key":"key2025121216553190395_59","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1090\/dimacs\/004\/41","article-title":"Stretchability of Pseudolines is NP-Hard.","volume":"4","author":"Shor, Peter W.","year":"1991","unstructured":"[59] Shor, Peter W. Stretchability of Pseudolines is NP-Hard., Applied Geometry And Discrete Mathematics (Gritzmann, Peter; Sturmfels, Bernd, eds.) (DIMACS Series in Discrete Mathematics and Theoretical Computer Science), Volume 4 (1991), pp. 531-554","journal-title":"Applied Geometry And Discrete Mathematics"},{"key":"key2025121216553190395_60","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2008.00492","author":"Skopenkov, Arkadiy","year":"2020","unstructured":"[60] Skopenkov, Arkadiy Extendability of simplicial maps is undecidable (2020)","journal-title":"Extendability of simplicial maps is undecidable"},{"issue":"3","key":"key2025121216553190395_61","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/050642368","article-title":"On the chromatic number of geometric hypergraphs","volume":"21","author":"Smorodinsky, Shakhar","year":"2007","unstructured":"[61] Smorodinsky, Shakhar On the chromatic number of geometric hypergraphs, SIAM Journal of Discrete Mathematics, Volume 21 (2007) no. 3, pp. 676-687","journal-title":"SIAM Journal of Discrete Mathematics"},{"issue":"2","key":"key2025121216553190395_62","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1006\/jagm.1994.1012","article-title":"Recognition of circle graphs","volume":"16","author":"Spinrad, Jeremy","year":"1994","unstructured":"[62] Spinrad, Jeremy Recognition of circle graphs, Journal of Algorithms, Volume 16 (1994) no. 2, pp. 264-282","journal-title":"Journal of Algorithms"},{"key":"key2025121216553190395_63","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2210.12817","author":"Stade, Jack","year":"2022","unstructured":"[63] Stade, Jack Complexity of the boundary-guarding art gallery problem (2022)","journal-title":"Complexity of the boundary-guarding art gallery problem"},{"key":"key2025121216553190395_64","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/3-540-58950-3_375","article-title":"Characterization and recognition of point-halfspace and related orders","author":"Tanenbaum, Paul J.","year":"1995","unstructured":"[64] Tanenbaum, Paul J.; Goodrich, Michael T.; Scheinerman, Edward R. Characterization and recognition of point-halfspace and related orders, Graph Drawing, Springer (1995), pp. 234-245","journal-title":"Graph Drawing"},{"key":"key2025121216553190395_65","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2209.05678","author":"Tuncel, Levent","year":"2022","unstructured":"[65] Tuncel, Levent; Vavasis, Stephen; Xu, Jingye Computational complexity of decomposing a symmetric matrix as a sum of positive semidefinite and diagonal matrices (2022)","journal-title":"Computational complexity of decomposing a symmetric matrix as a sum of positive semidefinite and diagonal matrices"}],"container-title":["Innovations in Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/igt.centre-mersenne.org\/item\/10.5802\/igt.9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T15:55:44Z","timestamp":1765554944000},"score":1,"resource":{"primary":{"URL":"https:\/\/igt.centre-mersenne.org\/articles\/10.5802\/igt.9\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,24]]},"references-count":65,"alternative-id":["10.5802\/igt.9"],"URL":"https:\/\/doi.org\/10.5802\/igt.9","relation":{},"ISSN":["3050-743X"],"issn-type":[{"value":"3050-743X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,24]]}}}