Conference abstracts

Session A4 - Computational Geometry and Topology

July 11, 17:30 ~ 17:55 - Room B7

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

Eric Sedgwick

DePaul University, School of Computing, USA   -

Let $\textsc{Embed}_{k\rightarrow d}$ be the problem of deciding whether a given $k$-dimensional complex admits a piecewise-linear embedding in $\mathbb R^d$. The complexity of solving this problem varies widely in the parameters $k$ and $d$: \textsc{Graph Planarity} ($\textsc{Embed}_{1\rightarrow 2}$) is solvable in linear time, but in higher dimensions, depending on the codimension, the problem can range from polynomial-time solvable ($d \geq 4, k < (2d-2)/3$), to \textbf{NP}-hard ($d \geq 4, d \geq k \geq (2d-2)/3$), to undecidable ($k \geq d-1 \geq 4$).

We show that $\textsc{Embed}_{2\rightarrow 3}$ and $\textsc{Embed}_{3\rightarrow 3}$ are \textbf{NP}-hard, which helps to clarify the picture in dimension 3. These two problems were only recently shown to be decidable and, like that work, our proof relies heavily on the theory of 3-manifolds.

Joint work with Arnaud de Mesmay (CNRS, GIPSA-Lab, France), Yo'av Rieck (University of Arkansas, USA) and Martin Tancer (Charles University, Czech Republic).

View abstract PDF

FoCM 2017, based on a nodethirtythree design.