Originator: Erik Demaine (presented by T. Grauman - REGS 2008)
Background: Given a collection of creases on a piece of paper, each assigned a folding direction of mountain (M) or valley (V), we want to determine whether it is possible to fold along these creases, respecting labels, until the paper is flat (when treated as paper with zero thickness). In particular, we consider the restricted case when the creases all lie along an orthogonal m×n grid and we want to fold the paper into a single 1×1 flat-folded square. We may think of a crease pattern as a straight-line embedding of a graph, allowing us to refer to creases as edges and to the intersection of creases as vertices.
Definitions: A vertex is flat-foldable if the four edges incident to it allow the 2×2 area around the vertex to be folded flat; this happens if and only if the labels on its incident edges consist of one of one type and three of the other type. A labeling of the edges of a grid is locally flat-foldable if every vertex is flat-foldable.
Two crease patterns for an m×n grid are equivalent if one
turns into the other under a succession of operations of three types:
1) Rotation: Rotation of the pattern by 90 degrees.
2) Mirror: Reflection of the pattern in a mirror.
3) Flip: The result of flipping over the paper.
Question 1: What is the number of equivalence classes of locally flat-foldable crease patterns for an m×n grid?
Definition: A labeling is globally flat-foldable if the physical process of achieving all the folds in the right direction can be achieved by some sequence of folds. Being locally flat-foldable is a necessary condition for being globally flat-foldable.
Question 2: Which locally flat-foldable patterns are globally flat-foldable?
References:
http://erikdemaine.org/papers/MapFolding/ (Website with pdf of paper as
well as all citation information)