Information Technology Reference
In-Depth Information
set of
x
-coordinates of vertices of
G
and add an extra “half”
x
-coordinate at the
midpoint between any two consecutive coordinate values. Subdivide each edge of
G
by adding vertices at all the
x
-coordinates in this set. The same subdivisions
can be made in any flat folding of
G
, so there is no change to the existence or
number of flat foldings. The subdivision does change the set of touching pairs,
but two edges of the original graph form a touching pair if and only if two of
the edges in the paths they are subdivided into form a touching pair, so the
correctness of the part of the theorem about touching pairs carries over.
With
G
subdivided in this way, we carry out the proof by induction on the
number of face angles that are assigned to be 360
ⓦ
(
mountain folds
). The base
case of the induction is the case in which
G
has only two such angles, on the outer
face. In this case every cycle consists of two paths of increasing
x
-coordinates and
has a unique flat folding, and it is easy to see that
G
has a flat folding with the
same touching pairs. (Equivalently, the graph in this case is a directed
st
-plane
graph so it is upward planar with each face drawn as two upward paths.)
If
G
contains a vertex
v
, and an interior face
f
in which
v
is a mountain fold,
then let
e
be one of the two edges of
f
incident to
v
, the one that is uppermost
in the magnified view of the flat folding edge corresponding to these two edges,
and let
e
be the edge immediately above that one. Edge
e
must exist, because if
e
were the topmost edge in this magnified view, then
f
would necessarily be the
exterior face. (For example, in Figure 6, vertex
g
is a mountain fold in a cycle;
edge
bg
is the uppermost edge incident to
g
;and
bc
is the edge immediately
above it.) Let
v
be the endpoint of
e
whose
x
-coordinate is the same as
v
.We
form a graph
G
by identifying
v
with
v
, ordering the edges of the combined
super-vertex so that
e
and
e
remain consecutive. This produces a graph, not a
multigraph, because the other endpoints of
e
and
e
are subdivision points at a
“half”
x
-coordinate, and so cannot coincide with each other. (In the example, we
would identify vertices
g
and
c
; the figure does not show the extra subdivision
points.) This vertex identification reduces the number of mountain folds by one
compared with
G
, and splits
f
into two simpler faces
f
1
and
f
2
. The same split
operation can be done to the flat folding of
f
, giving flat foldings of
f
1
and
f
2
.
Thus,
G
meets the conditions of the theorem and has fewer mountain folds; by
induction it has a flat folding realizing all the touching pairs of its face foldings,
which are the same as the touching pairs of the face foldings of
G
.Inthisflat
folding, the supervertex of
G
formed from
v
and
v
can be split back into the
two separate vertices
v
and
v
, giving the desired flat folding of
G
.
The case when there exist three or more mountain folds on the exterior face
is similar, but we must be more careful in our choice of
v
. Each mountain folded
vertex on the exterior face is either a local minimum or local maximum of
x
-
coordinates; because there are three or more of them, we may choose
v
to be a
vertex that is not a unique global extremum. Then, as above, we find a vertex
v
with the same coordinate, above or below
v
,andmerge
v
and
v
into a single
vertex, giving a graph
G
with fewer mountain folds in which the outer face has
been split into two faces, one outer and one inner. As before, these two faces
inherit a flat folded state from the given flat folding of the outer face of
G
,soby
