Embeddability in $\mathbb{R}^3$ is NP-hard
From MaRDI portal
Publication:4607974
zbMath1403.68322arXiv1708.07734MaRDI QIDQ4607974
Yo'av Rieck, Eric Sedgwick, Martin Tancer, Arnaud de Mesmay
Publication date: 15 March 2018
Full work available at URL: https://arxiv.org/abs/1708.07734
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
57Q35: Embeddings and immersions in PL-topology