Information Technology Reference
In-Depth Information
induction
G
has a flat folding. And as before,
v
and
v
may be split back into
separate vertices in this flat folding, giving the desired flat folding of
G
.
4 Algorithm to Find a Folding
For completeness, we briefly describe a greedy “crimping” strategy for find-
ing flat-folded states of simple cycles with pre-assigned fold angles. Bern and
Hayes [6] used a similar strategy to flat-fold cycles without pre-assigned angles.
Arkin et al. [4] applied this method to open polygonal chains with assigned an-
gles. The version here for cycles with assigned angles is described by Demaine
and O'Rourke [12]. We do not describe its (non-trivial) correctness proof.
First, remove any flat folds from the input by merging the edges on either
side of the fold. Then, repeatedly find an edge
e
such that the two edges on
either side of
e
are at least as long as
e
, with folds of opposite type at its ends.
If no such edge
e
exists, the cycle has no folding. If an edge
e
that meets these
conditions can be found, it is safe to perform both folds, merging
e
with its two
neighboring edges into a single edge of a simpler polygon.
Maintaining a set of edges that are ready to be folded, and performing each
fold, takes constant time per fold, so folding a cycle in this way, and recovering
the covering relation of its ordered line embedding, may be done in linear time.
Putting the characterization from Section 3 together with the algorithm for
folding a single cycle described above gives us an algorithm for testing whether
a given plane graph
G
with edge length and angle assignment is flat foldable:
Theorem 2.
We can test flat foldability of a plane graph with given edge lengths
and given angle assignment in linear time.
Proof.
We partition the graph into its component faces, and apply the crimping
algorithm to an Euler tour of each face. Each face takes time proportional to its
size, so the total time is linear. For the correctness of forming simple cycles from
each face by taking Euler tours, see the full version of this paper.
5 Counting Flat Foldings
We cannot use crimping to count the flat foldings of a cycle, because some flat
foldings cannot be formed by a sequence of crimping steps (Figure 7). Instead,
to count flat foldings in a single cycle, we use dynamic programming.
Lemma 1 (proof in the full version of this paper).
Given a single n-vertex
cycle, with an assignment of edge lengths and angles, it is possible to count the
flat foldings of the cycle in time O
(
n
5
)
.
Theorem 3.
We can count the flat foldings of an n-vertex planar graph G with
an assignment of edge lengths and angles in time O
(
n
5
)
.
Proof.
We apply Lemma 1 to the Euler tour of each face of
G
and return the
product of the resulting numbers.
