The complexity of recognizing geometric hypergraphs

DOI10.1007/978-3-031-49272-3_12MaRDI QIDQ6560147

Daniel Bertschinger, Nicolas El Maalouly, Linda Kleist, Tillmann Miltzow, Simon Weber

Publication date: 21 June 2024

computational complexity hypergraph ellipsoid recognition convex ball geometric hypergraph halfspace halfplane

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Sphere and dot product representations of graphs
Fixed points, Nash equilibria, and the existential theory of the reals
Hardness of embedding simplicial complexes in $\mathbb R^d$
The complexity of tensor rank
$\epsilon$-nets and simplex range queries
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
Intersection graphs of segments
Extremal problems for geometric hypergraphs
The complexity of drawing a graph in a polygonal region
Integer realizations of disk and segment graphs
Representing graphs and hypergraphs by touching polygons in 3D
Algorithmic solvability of the lifting-extension problem
Optimal greedy algorithms for indifference graphs
Extendability of simplicial maps is undecidable
Realizability of Graphs and Linkages
Density of range capturing hypergraphs
Embeddability in the 3-Sphere Is Decidable
Computing All Maps into a Sphere
ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria
On The Chromatic Number of Geometric Hypergraphs
Complexity of Some Geometric and Topological Problems
Recognition of Circle Graphs
Intersection Graphs of Rays and Grounded Segments
On Restricted Nonnegative Matrix Factorization
A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
Existential-R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games
Realization spaces of 4-polytopes are universal
Tight lower bounds for the size of epsilon-nets
Embeddability in R ³ is NP-hard
Complexity of Geometric k-Planarity for Fixed k
Polynomial-Time Computation of Homotopy Groups and Postnikov Systems in Fixed Dimension
The art gallery problem is ∃ ℝ-complete
The Complexity of Positive Semidefinite Matrix Factorization
Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
Recognizing string graphs in NP
On the computational complexity of decision problems about multi-player Nash equilibria
The complexity of the Hausdorff distance
Completeness for the complexity class $\forall \exists \mathbb{R}$ and area-universality

This page was built for publication: The complexity of recognizing geometric hypergraphs