Information Technology Reference
In-Depth Information
Tabl e 1.
Complexity of flat folding a plane graph, by input model
Flat angles forbidden
Flat angles allowed
Angle assignment given
Linear time (new)
Linear time (new)
Angle assignment unspecified
Open
NP-complete [2]
the subset sum problem. For general plane graphs, the problem becomes strongly
NP-complete [2]. Therefore, we concentrate in this paper on the version of the
problem with given angle assignments, posed as an open problem in [2].
1.1 New Results
We show that it is possible to test in linear time whether a given plane graph,
with given edge lengths and angle assignment, can be folded flat; refer to Table 1.
Additionally, in polynomial time, we can count the number of combinatorially
distinct flat foldings.
Our algorithms are based on a new characterization of flat-foldable graphs: a
flat folding exists if and only if the angles at each vertex sum to 360
ⓦ
and each
individual face in the given graph can be folded flat. Even stronger, we show that
independent flat foldings of the interior of each face can always be combined into
a flat folding of the whole graph. Figure 3 shows an example of this combination
of face foldings. A form of the theorem was conjectured in 2001 by Ilya Baran,
Erik Demaine, and Martin Demaine, but not proved until now; it contradicts the
intuitive (but false) idea that, for faces with ambiguous spiraling shapes, each
face must be folded consistently with its neighboring faces. With this theorem in
hand, our algorithms for constructing and counting folded states follow by using
a greedy “crimping” strategy for flat-folding simple cycles [4,6,12] and by using
dynamic programming to count cycles within each face.
Our characterization necessarily concerns flat folded states, not continuous
folding motions from a given (nonflat) configuration. As shown by past work,
even for trees, there exist locked states that cannot be continuously moved to a
flat folded state [5,8], and testing the existence of a continuous motion between
two states is PSPACE-complete [3].
We leave open the problem of finding a flat folded state for a graph in which
the planar embedding and edge lengths are preassigned, and angles of 180
ⓦ
are
forbidden, but the choice of which angles at each vertex are 0 and which are
360
ⓦ
is left free (bottom-left cell of Table 1). Even for trees, this open problem
appears to be nontrivial; see Figure 4 and [15].
1.2 Related Work
There has been intensive study of straight-line drawings of graphs with specified
edge lengths and/or specified angles between consecutive edges in a cyclic order-
ing of edges around each vertex. If only edge lengths are specified then—whether
the drawing must be planar or not—the problem is NP-hard [9,24], or worse [25].
