**Reference**:- Zachary Abel and Erik D. Demaine, “Edge-Unfolding Orthogonal Polyhedra is Strongly NP-Complete”, in
*Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011)*, Toronto, Ontario, Canada, August 10–12, 2011, to appear. **Abstract**:- 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.
**Length**:- The paper is 6 pages.
**Availability**:- The paper is available in PDF (293k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.