The complexity of recognizing geometric hypergraphs

DOI10.1007/978-3-031-49272-3_12MaRDI QIDQ6560147zbMATH OpenFDO

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

Publication date 21 June 2024

Full work available at URL https://doi.org/10.1007/978-3-031-49272-3_12

zbMATH Keywords

computational complexityballhypergraphrecognitionconvexellipsoidgeometric hypergraphhalfspacehalfplane

Mathematics Subject Classification ID

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 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 -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
• -nets and simplex range queries
• \(\exists\mathbb{R}\)-complete decision problems about symmetric Nash equilibria in symmetric multi-player games

Cited in

(1)

• The complexity of recognizing geometric hypergraphs

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)