The last of my Graph Drawing preprints is also the first of the papers to see daylight from the workshop last spring in Barbados: "Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths" (arXiv:1408.6771, with Zachary Abel, Erik Demaine, Martin Demaine, Anna Lubiw, and Ryuhei Uehara).

It's part of what has become a long line of research on trying to understand which shapes can be squashed flat, starting with Maekawa's theorem (every vertex of a flat-folded sheet of paper has to have numbers of mountain folds and valley folds that differ by two) and Kawasaki's theorem (alternating angles at each vertex must sum to \( \pi \)). If you have a piece of paper with a desired set of fold lines marked on it, and these fold lines all converge on a single vertex, then it's possible to exactly characterize whether you can fold it flat along those lines. A greedy algorithm can find a way to fold it efficiently, and a version of the Carpenter's rule theorem implies that, when a flat-folded state exists, you can always get to it by a continuous motion. But as Bern and Hayes showed at SODA 1996, the restriction to a single vertex is crucial: the folds at different vertices can interact with each other in complicated ways, making flat foldability of multi-vertex folding patterns NP-complete.

The new paper follows an earlier one at ISAAC 2011 and IJCGA 2013, "Folding equilateral plane graphs", by an overlapping set of authors, in studying the flat-foldability of objects that are not just flat sheets of paper. But in order to avoid Bern and Hayes' NP-hardness proof, we again restrict our attention only to objects with a single vertex. That is, we have some sort of complex of flat polygons connected by piano hinges at their edges, but all the hinges meet at a point. As in the following illustration:

A single-vertex polygon complex, with hinged edges

The blue sphere highlights the vertex, but it also indicates a way to think of the problem in only two dimensions instead of three: cut the complex through the surface of the sphere so that each polygon turns into a line segment (or really a segment of a great circle), each hinge turns into a point, and what you have is just a planar graph drawing. The line segments are rigid but the hinges at their endpoints make the whole drawing floppy (within the plane it's defined in). The question is whether it is sufficiently floppy that it can be made to lie flat along a line.

Our key insight is in some sense the opposite of Bern and Hayes': the folds within different faces of this planar graph cannot interact with each other at all. This is not obvious, or at least it wasn't to us. But with this in hand, the rest is easy: we already know how to flatten things with one face using the results about folding patterns on flat sheets of paper, so to test whether a complex can be flattened we just need to test each of its faces separately. By using dynamic programming within each face and then multiplying the results, we can also count the number of different flat-folded states.