Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality
DOI10.1007/s00454-022-00381-0arXiv1712.05142OpenAlexW3212404018MaRDI QIDQ6156090
Linda Kleist, Tillmann Miltzow, Paweł Rzążewski, Michael Gene Dobbins
Publication date: 12 June 2023
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1712.05142
planar graphexistential theory of the realscomplexity classarea-universalityface areauniversal existential theory of the reals
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph representations (geometric and intersection representations, etc.) (05C62) Real algebraic and real-analytic geometry (14P99)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sphere and dot product representations of graphs
- Fixed points, Nash equilibria, and the existential theory of the reals
- Coloring face hypergraphs on surfaces
- Graph minors. XX: Wagner's conjecture
- Realizability of graphs
- Realizability of graphs in three dimensions
- Real quantifier elimination is doubly exponential
- Straightening polygonal arcs and convexifying polygonal cycles
- \(\forall\exists\mathbb {R}\)-completeness and area-universality
- Intersection graphs of rays and grounded segments
- Table cartogram
- On the area-universality of triangulations
- The complexity of drawing a graph in a polygonal region
- Mnëv's universality theorem revisited
- Drawing planar 3-trees with given face areas
- Integer realizations of disk and segment graphs
- Realizability of Graphs and Linkages
- Area-Universal and Constrained Rectangular Layouts
- The complexity of computing a Nash equilibrium
- Drawing Planar Graphs with Prescribed Face Areas
- Complexity of Some Geometric and Topological Problems
- Floorplans, planar graphs, and layouts
- Plane Cubic Graphs with Prescribed Face Areas
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- Drawing planar graphs with prescribed face areas
- Realization spaces of 4-polytopes are universal
- Recognizing Weak Embeddings of Graphs
- Smoothing the Gap Between NP and ER
- The art gallery problem is ∃ ℝ-complete
- Exploiting Air-Pressure to Map Floorplans on Point Sets
- The complexity of theorem-proving procedures
- On Area-Universal Quadrangulations
- Geometric Simultaneous Embeddings of a Graph and a Matching
- Algorithms in real algebraic geometry
