Embeddability in R^3 is NP-hard

zbMATH Open1403.68322arXiv1708.07734MaRDI QIDQ4607974FDOQ4607974

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

Publication date: 15 March 2018

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.

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

Recommendations

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

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)

Cited In (17)

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

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)