Information Technology Reference
In-Depth Information
us an input to the level planarity problem with a prescribed plane embedding.
However, the embeddings we seek in the folding problem are not the same as
level planar embeddings. In a level planar embedding, vertices within a single
level must be linearly ordered by the second coordinate value. In contrast, in the
folding problem a vertex that has only incoming or only outgoing edges may be
nested between two adjacent edges of another vertex at the same level. A four-
vertex cycle, oriented with alternating edge directions, illustrates the difference
between these two types of embedding: it is not level planar, but it still has a
flat folding with three mountain folds and one valley fold, corresponding to the
usual way of folding a square sheet of paper into quarters (Figure 5).
We have therefore been unable to apply level planarity algorithms to solve
our flattening problem. On the other hand, our algorithm can be used to test
level planarity of a plane graph (with a linear order of incoming and outgo-
ing edges at each vertex) in linear time. Given an input to the level planarity
problem, we assign increasing coordinates to the levels, and assign the length of
an edge to be the difference in coordinates between the levels of its endpoints.
Mountain/valley/flat angles are determined from the level assignment. Finally,
to preclude the nesting of vertices that is allowed in flattening but not in level
planarity, we add an extra edge incident to each vertex that has only incoming
or only outgoing edges: if vertex
v
on level
i
has only outgoing edges, we add a
new incoming edge from a new level just before
i
. The resulting plane graph has
a flat-folding respecting the angles and edge-lengths if and only if the original
has a level planar drawing. From this we also obtain the result that a leveled
plane graph has a level planar drawing if and only if each cycle does.
Rectilinear Planarity.
In our flat folding problem, the angles are multiples of
180
ⓦ
. When angles are multiples of 90
ⓦ
, we arrive at the important problems
of orthogonal and rectilinear graph drawing [14]. A graph is
rectilinear planar
if it can be drawn in the plane so that every edge is a horizontal or vertical
line segment. Coincident edges are forbidden, so the graph must have maximum
degree 4. This problem is NP-complete in general [18] but—as with upward
planarity—there is a polynomial time algorithm, due to Tamassia [27], if the
cyclic order of edges around vertices is prescribed. Again, the main issue is to
find an assignment of angles or, equivalently, a labeling of the edges incident
to a vertex with distinct labels from the set
U,D,L,R
,where
U
stands for
“Up”, etc. Tamassia finds the angles using network flows (in fact, he solves
a more general problem of minimizing the number of bends in the drawing).
At the heart of this method is the result that, given an angle assignment that
is locally consistent (i.e., the angles at every vertex sum to 360
ⓦ
), the graph
has a rectilinear planar drawing if and only if each face cycle does [27]. As
in the other cases we have discussed, the proof shows the stronger result that
embedding choices for the faces can be combined arbitrarily. A cycle with an
angle assignment has a rectilinear planar drawing if and only if the number of
right turns minus the number of left turns is 4 in a clockwise traversal inside the
cycle [27,28].
