The complexity of recognizing geometric hypergraphs

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

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

Publication date: 21 June 2024

Recommendations

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

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)

Cites Work

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

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)