Geometric embeddability of complexes is -complete

DOI10.4230/LIPICS.SOCG.2023.1MaRDI QIDQ6620487zbMATH OpenFDO

Authors Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow

Publication date 16 October 2024

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2023.1

zbMATH Keywords

existential theory of the realsgeometric embeddinghypergraphlinear embeddingrecognitionsimplicial complex

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• scientific article; zbMATH DE number 7051255
• Hardness of embedding simplicial complexes in R^d
• Embeddability in \(\mathbb R^3\) is NP-hard
• Hardness of almost embedding simplicial complexes in \(\mathbb {R}^d\)
• Embeddability in R^3 is NP-hard

Cited in

(7)

• On the complexity of recognizing nerves of convex sets
• Framework for \(\exists\mathbb{R}\)-completeness of two-dimensional packing problems
• Geometric thickness of multigraphs is \(\exists \mathbb{R}\)-complete
• A higher dimensional version of Fáry's theorem
• The complexity of recognizing geometric hypergraphs
• On colorings of hypergraphs embeddable in \(\mathbb{R}^d\)
• Constrained nonnegative Gram feasibility is \(\exists \mathbb{R}\)-complete

This page was built for publication: Geometric embeddability of complexes is \(\exists\mathbb{R}\)-complete

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