Edge-Unfolding Orthogonal Polyhedra is Strongly NP-Complete
Zachary Abel, Erik D. Demaine · 2011
We prove that it is strongly NP-complete to decide whether a given orthogonal polyhedron has a (nonoverlapping) edge unfolding. The result holds even when the polyhedron is topologically convex, i.e., is homeomorphic to a sphere, has faces that are homeomorphic to disks, and where every two faces share at most one edge. 1