Information Technology Reference
In-Depth Information
c
o
d
b
c
d
b
d
a
a
b
o
c
a
Fig. 1.
Flat folding at a single vertex on a disc reduces to the problem of folding a
polygon onto a line
d
o
o
c
b
b
c
d
c
d
a
b
a
a
Fig. 2.
Flat folding a two-dimensional cell complex with a single vertex reduces to the
problem of folding a plane graph onto a line
from the unfolded piece of paper by a continuous motion that avoids bending or
folding the uncreased parts of the paper.
In practical applications of folding beyond origami, the object being folded
may not be a single flat sheet, but rather some 2D polyhedral cell complex with
nonmanifold topology (more than two facets joined at an edge). Flat foldability
of such complexes is no easier than the origami case, but again we can hope
for reduced complexity when a complex has only a single vertex. As with one-
vertex origami, we can reduce the problem to 1D by slicing with a small sphere
centered at the vertex—now resulting in a general plane graph rather than a
simple cycle—and asking whether this graph can be flattened onto a line [2]; see
Figure 2. In this way, the problem of flat-folding single-vertex complexes can be
reduced to finding embeddings of a given plane graph onto a line.
It is this problem that we study here: given a plane graph with specified edge
lengths, does it have a straight-line plane embedding with all vertices arbitrarily
close to a given line and with all edges arbitrarily close to their specified lengths?
In the version of the problem we study, we are additionally given a specification
of whether the angle between every two consecutive edges at each vertex is a
mountain fold
(the angle is arbitrarily close to 360
ⓦ
), a
valley fold
(the angle is
arbitrarily close to 0), or
flat
(the angle is arbitrarily close to 180
ⓦ
). Without this
information, the problem of testing whether a given plane graph can be folded
flat with specified edge lengths (allowing angles of 180
ⓦ
) is weakly NP-complete,
even for graphs that are just simple cycles, by a straightforward reduction from
