Embeddability in ${\mathbb{R}}^3$ is NP-hard

Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick +1

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-…