Information Technology Reference
In-Depth Information
p
q
r
s
c
b
b
c
d
a
g
a
d
e
g
f
e
f
p
q
r
s
Fig. 6.
A flat-folding of a seven-vertex graph
G
(left), described as a self-touching
configuration in which
G
is mapped onto a four-vertex path
H
(right), shown with
magnified views of its edges and vertices of
H
.
each other. A
face
of a flat folding or self-touching configuration is a cycle formed
by a face of the expanded drawing. The
angle
formed by a pair of incident edges
in a flat folding is one of three values, 0, 180
ⓦ
, or 360
ⓦ
, accordingly as the face lies
between the two edges, the two edges extend in opposite directions from their
common endpoint, or the two edges extend in the same direction with the face
on both sides of them. An
angle assignment
to a plane graph is an assignment
of the values 0, 180
ⓦ
, or 360
ⓦ
to each of its angles, regardless of whether this
assignment is compatible with a flat-folding of the graph. An angle assignment
is
consistent
if the angles sum to 360
ⓦ
at every vertex.
We define a
touching pair
of edges in a self-touching configuration of a graph
G
to be two edges
e
and
f
of
G
such that these two edges are consecutive in the
magnified view of at least one edge in
H
. Each touching pair can be assigned to
a single face of
G
, the face that lies between the two edges.
3 Local Characterization
In this section we show that for a plane graph with assigned lengths and consis-
tent angles, being able to fold the whole graph flat is equivalent to being able to
fold each of its faces flat.
Theorem 1.
Let G be a plane graph with given edge lengths and a consistent
angle assignment. Then G has a flat folding if and only if every face cycle of
G (with the induced assignment of lengths and angles) has a flat folding. More
strongly, for every combination of flat foldings of the faces of G,thereexistsa
flat folding of G itself whose touching pairs for each face are exactly the ones
given in the folding of that face.
Proof.
One direction is straightforward: if
G
has a flat folding, then restricting
to the faces of
G
gives flat foldings of the faces with the same touching pairs.
For the other direction, assume we have flat foldings of the faces of
G
.We
will show that
G
has a flat folding with the same touching pairs. As described
in Section 1.2, the assignment of lengths and angles given with
G
(together with
an arbitrary choice of an
x
coordinate for one vertex and an orientation for one
edge) gives us a unique assignment of
x
coordinates for the vertices of
G
in any
possible flat folding. We will start by subdividing all the edges of
G
.Takethe
