This glued simple polygon is called a net . A net for the cube. A beautiful and surprising result of Aleksandrov is that the converse is true as well. This actually requires solving two separate subproblems. Note that the crease pattern, and thus the resulting polytope, depends on the geometric shape of the net as well as its combinatorial structure.
Colors indicate the resulting polytope facets.
Boris Aronov and Joe O'Rourke observed that we can obtain a superset of the creases by finding all shortest paths, in the polyhedral metric defined by the net, between every pair of vertices. All shortest paths from one vertex and all shortest paths between every pair of vertices on the cube net. If two polytopes have the same faces and the same adjacency pattern, they are called stereoisomers . Cauchy's proof is nonconstructive. Although a numerical approximation algorithm seems quite likely, I would be much happier with a purely combinatorial algorithm that runs in polynomial time.