Embeddability in R^3 is NP-hard

MaRDI QIDQ4607974zbMATH OpenFDO

Authors Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick, Martin Tancer

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1708.07734, http://dl.acm.org/citation.cfm?id=3175356

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Embeddings and immersions in PL-topology (57Q35)

Abstract: We prove that the problem of deciding whether a 2- or 3-dimensional simplicial complex embeds into $mathbb{R}^3$ is NP-hard. Our construction also shows that deciding whether a 3-manifold with boundary tori admits an $mathbb{S}^3$ filling is NP-hard. The former stands in contrast with the lower dimensional cases which can be solved in linear time,and the latter with a variety of computational problems in 3-manifold topology (for example, unknot or 3-sphere recognition, which are in NP and co-NP assuming the Generalized Riemann Hypothesis). Our reduction encodes a satisfiability instance into the embeddability problem of a 3-manifold with boundary tori, and relies extensively on techniques from low-dimensional topology, most importantly Dehn fillings on link complements.

Recommendations

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

Cited in

(17)

• Geometric embeddability of complexes is \(\exists\mathbb{R}\)-complete
• Hardness of embedding simplicial complexes in R^d
• New constructions related to the polynomial sphere recognition problem
• Homological reconstruction and simplification in \(\mathbb{R}^3\)
• scientific article; zbMATH DE number 7051255 (Why is no real title available?)
• The unbearable hardness of unknotting
• Atomic Embeddability, Clustered Planarity, and Thickenability
• Finding non-orientable surfaces in 3-manifolds
• scientific article; zbMATH DE number 7559249 (Why is no real title available?)
• Invariants of graph drawings in the plane
• scientific article; zbMATH DE number 6381680 (Why is no real title available?)
• Finding non-orientable surfaces in 3-manifolds
• Hardness of almost embedding simplicial complexes in \(\mathbb {R}^d\)
• Embeddability in \(R^3\) is NP-hard
• Graph Drawing
• Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete
• Adjacency graphs of polyhedral surfaces

This page was built for publication: Embeddability in \(\mathbb R^3\) is NP-hard

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