On the complexity of recognizing nerves of convex sets

DOI10.57717/CGT.V3I2.40MaRDI QIDQ6124760zbMATH OpenFDO

Authors Patrick Schnider, Simon Weber

Publication date 2 April 2024

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2302.13276

zbMATH Keywords

existential theory of the realsintersection graphsnerverecognition

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Analysis of algorithms and problem complexity (68Q25) 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
• Nerves of good covers are algorithmically unrecognizable
• Geometric embeddability of complexes is \(\exists\mathbb{R}\)-complete
• Intersection Patterns of Convex Sets via Simplicial Complexes: A Survey

Cites work

• D-collapsibility is NP-complete for d 4
• A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
• Complexity of some geometric and topological problems
• Fixed points, Nash equilibria, and the existential theory of the reals
• scientific article; zbMATH DE number 4092241 (Why is no real title available?)
• Integer realizations of disk and segment graphs
• Intersection graphs of segments
• On restricted nonnegative matrix factorization
• Representing graphs and hypergraphs by touching polygons in 3D
• Smoothing the Gap Between NP and ER
• Some provably hard crossing number problems
• 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 ∃ℝ-complete

Cited in

(1)

• The complexity of recognizing geometric hypergraphs

This page was built for publication: On the complexity of recognizing nerves of convex sets

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