Information Technology Reference
In-Depth Information
Flat Foldings of Plane Graphs
with Prescribed Angles and Edge Lengths
Zachary Abel
1
,ErikD.Demaine
2
, Martin L. Demaine
2
, David Eppstein
3
,
Anna Lubiw
4
, and Ryuhei Uehara
5
1
Department of Mathematics, MIT, Cambridge, USA
2
MIT Computer Science and Artificial Intelligence Lab., Cambridge, USA
3
Department of Computer Science, University of California, Irvine, USA
4
David R. Cheriton School of Computer Science, University of Waterloo, Canada
5
School of Information Science, Japan Advanced Institute of Science and
Technology, Ishikawa, Japan
Abstract.
When can a plane graph with prescribed edge lengths and
prescribed angles (from among
{
0
,
180
ⓦ
,
360
ⓦ
}
) be folded flat to lie in
an infinitesimally thick line, without crossings? This problem generalizes
the classic theory of single-vertex flat origami with prescribed mountain-
valley assignment, which corresponds to the case of a cycle graph. We
characterize such flat-foldable plane graphs by two obviously necessary
but also su
cient conditions, proving a conjecture made in 2001: the
angles at each vertex should sum to 360
ⓦ
, and every face of the graph
must itself be flat foldable. This characterization leads to a linear-time
algorithm for testing flat foldability of plane graphs with prescribed edge
lengths and angles, and a polynomial-time algorithm for counting the
number of distinct folded states.
1 Introduction
The modern field of origami mathematics began in the late 1980s with the goal
of characterizing flat-foldable crease patterns, i.e., which plane graphs form the
crease lines in a flat folding of a piece of paper [12]. This problem turns out to be
NP-complete in the general case, with or without an assignment of which folds
are mountains and which are valleys [6].
On the other hand, flat foldability can be solved in polynomial time for crease
patterns with just a single vertex (thus characterizing the local behavior of a
vertex in a larger graph). By slicing the paper with a small sphere centered at
the single vertex (the geometric
link
of the vertex), single-vertex flat foldabil-
ity reduces to the 1D problem of folding a polygon (closed polygonal chain)
onto a line; see Figure 1. This problem can be solved by a greedy algorithm
that repeatedly folds both ends of a shortest edge with opposite fold directions
(mountain and valley)—either because such directions have already been pre-
assigned or, if the mountain-valley assignment is not given, by making such
an assignment [4,6,12,20]. The spherical, self-touching Carpenter's Rule Theo-
rem [1,11,26] implies that any flat-folded single-vertex origami can be reached
