The complexity of recognizing geometric hypergraphs

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

Recommendations

Complexity of some geometric and topological problems
On the complexity of recognizing nerves of convex sets

Cites work

scientific article; zbMATH DE number 4092241 (Why is no real title available?)
scientific article; zbMATH DE number 17663 (Why is no real title available?)
scientific article; zbMATH DE number 1520171 (Why is no real title available?)
A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
Algorithmic solvability of the lifting-extension problem
Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality
Complexity of geometric \(k\)-planarity for fixed \(k\)
Complexity of some geometric and topological problems
Computing all maps into a sphere
Density of range capturing hypergraphs
ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
Embeddability in \(R^3\) is NP-hard
Extendability of simplicial maps is undecidable
Extremal problems for geometric hypergraphs
Fixed points, Nash equilibria, and the existential theory of the reals
Hardness of embedding simplicial complexes in \(\mathbb R^d\)
Integer realizations of disk and segment graphs
Intersection graphs of rays and grounded segments
Intersection graphs of segments
On The Chromatic Number of Geometric Hypergraphs
On restricted nonnegative matrix factorization
On the computational complexity of decision problems about multi-player Nash equilibria
Optimal greedy algorithms for indifference graphs
Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension
Realizability of graphs and linkages
Realization spaces of 4-polytopes are universal
Recognition of Circle Graphs
Recognizing string graphs in NP
Representing graphs and hypergraphs by touching polygons in 3D
Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes
Sphere and dot product representations of graphs
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
The art gallery problem is \(\exists \mathbb{R}\)-complete
The complexity of drawing a graph in a polygonal region
The complexity of positive semidefinite matrix factorization
The complexity of tensor rank
The complexity of the Hausdorff distance
Tight lower bounds for the size of epsilon-nets
\(\epsilon\)-nets and simplex range queries
\(\exists\mathbb{R}\)-complete decision problems about symmetric Nash equilibria in symmetric multi-player games

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6560147)