When can you fold a map? (Q1883580)

A crease pattern is a straight-edge embedding of a graph on a polygonal piece of paper, usually with specified mountain and valley assignments that give a folding direction; a flat folding must fold along all the edges of the graph, but no more. Characterizing flat-foldable crease patterns is the best-studied problem in origami mathematics and has a natural algorithmic counterpart consisting of determining whether a given crease pattern is flat-foldable. In this paper it is proved that deciding foldability of an orthogonal crease pattern on a rectangular piece of paper can be done in linear time, while slight variations, like having a general orthogonal piece of paper, 45-degree creases, or no mountain/valley assignment, gives NP-complete problems.