Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths - Graph Drawing - page 275

Fig. 4. A tree with fixed edge lengths that (when angles equal to 180 ⓦ are forbidden)
has no flat folding, regardless of planar embedding or angle assignment
vertices with only incoming or only outgoing edges, where exactly one angle
should be large and the rest small. Bertolazzi et al. used network flows to de-
termine these angles. To prove their algorithm's correctness, they showed that a
graph with a given angle assignment has an upward planar drawing if and only if
each face cycle has an upward planar drawing. The condition for drawing a single
face, given an angle assignment, is particularly simple: an acyclic orientation of
a cycle has an upward planar drawing if and only if it has two more small than
large angles. Their proof also shows that embedding choices for the faces can be
combined arbitrarily.
Level Planarity. Our flat folding problem differs from upward planarity in that
we have assigned edge lengths as well as assigned angles. This makes it more
similar to the problem of level planarity [13,19,21]. The input to this problem is a
leveled directed acyclic graph: a DAG whose vertices have been partitioned into
a sequence of levels (independent sets of its vertices), with all edges directed
from earlier to later levels. The goal is to find an upward planar embedding
that places the vertices of each level on a horizontal line [22]. This problem has
a linear time solution [21] based on PQ-trees. When the cyclic order of edges
around vertices is specified (and in fact for more general constraints) there is a
quadratic time solution based on solving systems of binary equations [19].
The input to our folding problem may be interpreted as a leveled plane DAG.
(Since our convention is to flatten to a horizontal line, we will map to a level
planarity problem with levels progressing rightward rather than upward—this is
a superficial difference.) Arbitrarily choose an x -coordinate for one vertex and
a direction (left-to-right) for one edge incident to that vertex. These choices
can be propagated to all the vertices and edges using the specified edge lengths
and angles. The set of vertices at a given x -coordinate constitute a level, giving
Fig. 5. A four-vertex cycle with vertices alternating between two levels is not level
planar, but can be folded flat, representing a sheet of paper folded into quarters.