Embeddability in $\mathbb{R}^3$ is NP-hard
From MaRDI portal
Publication:4607974
zbMath1403.68322arXiv1708.07734MaRDI QIDQ4607974
Martin Tancer, Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick
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
Related Items
Unnamed Item, Atomic Embeddability, Clustered Planarity, and Thickenability, Invariants of graph drawings in the plane, New constructions related to the polynomial sphere recognition problem, The unbearable hardness of unknotting