next up previous
Next: Problem 65: Magic Configurations Up: The Open Problems Project Previous: Problem 63: Dynamic Planar

Problem 64: Edge-Unfolding Polycubes

Is there any genus-zero orthogonal polyhedron P built by gluing together cubes face-to-face that cannot be edge-unfolded, where all cube edges on the surface of P are considered edges available for cutting? These orthogonal polyhedra are sometimes known as polycubes, 3D versions of 2D polyominoes.
George Hart and Joseph O'Rourke, 2004.
More general problems seem even more difficult.
Partial and Related Results
This is a special case of a more general problem, which is equally open. The goal, as in Problem 9, is to cut the surface and unfold without overlap. An edge unfolding only permits cutting along edges of the polyhedron. A grid unfolding adds extra edges to the surface by intersecting the polyhedron with planes parallel to coordinate planes through every vertex, and so is easier to edge-unfold. Easier still is the posed problem: The orthogonal polyhedron is built from cubes, and all cube edges are available for cutting. Is there any such polyhedron that cannot be edge-unfolded? Such an example would narrow the options, but it may be that every orthogonal polyhedron can be grid-unfolded. (An easy box-on-box example [BDD+98] shows that without some surface refinement [DO05], not all orthogonal polyhedra can be edge-unfolded.) The posed question is among the most specific whose answer would make progress.

Only a few narrow subclasses of orthogonal polyhedra are known to have grid-unfolding algorithms: orthotubes, orthostacks of orthogonally convex slabs, and orthogonal terrains. See [O'R08].

Related Open Problems
Problem 9: Edge-Unfolding Convex Polyhedra.
Problem 42: Vertex-Unfolding Polyhedra.
Problem 43: General Unfolding of Nonconvex Polyhedra.
folding and unfolding; polyhedra
Entry Revision History
J. O'Rourke, 14 Jul 2006, 16 Jul 2007.


Therese Biedl, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke, Mark Overmars, Steve Robbins, and Sue Whitesides.
Unfolding some classes of orthogonal polyhedra.
In Proc. 10th Canad. Conf. Comput. Geom., pages 70-71, 1998.
Full version in Elec. Proc.:

Erik D. Demaine and Joseph O'Rourke.
Geometric Folding Algorithms: Linkages, Origami, Polyhedra.
Cambridge University Press, 2007.
In press. (formerly

Erik D. Demaine and Joseph O'Rourke.
Open problems from CCCG 2004.
In Proc. 17th Canad. Conf. Comput. Geom., pages 303-306, 2005.

Joseph O'Rourke.
Unfolding orthogonal polyhedra.
In J.E. Goodman, J. Pach, and R. Pollack, editors, Proc. Snowbird Conference Discrete and Computational Geometry: Twenty Years Later, pages 307-317. American Mathematical Society, 2008.

next up previous
Next: Problem 65: Magic Configurations Up: The Open Problems Project Previous: Problem 63: Dynamic Planar
The Open Problems Project - December 04, 2015