Information Technology Reference
In-Depth Information
Our result on flat folding can be used to prove an extension of the above result
to rectilinear graph drawings with angles specified and with lengths assigned to
the “horizontal” edges. (Note that the angle information allows us to distinguish
the two classes of edges, although it is arbitrary which class is horizontal and
which is vertical.) Given a rectilinear plane graph, contract all vertical edges,
assigning angles of 0 , 180 , 360 in the obvious way. Finally, in order to avoid
“nested” vertices at the same coordinate (as in Figure 5), we use the same trick
of adding an extra edge incident to each vertex that has only incoming or only
outgoing edges. We claim that the resulting multi-graph has a flat-folding if and
only if the original has a rectilinear planar drawing with horizontal edges of the
specified lengths. For the non-trivial direction, suppose we have a flat folding of
the constructed graph. We must expand each vertex to a vertical line segment
with the horizontal edges touching the line segment in a way that is consistent
with the original graph. This can easily be done in a left to right sweep.
From this reduction we obtain the following result.
Corollary 1. If G is a plane graph of maximum degree 4 with specified angles
that sum to 360 at each vertex and with lengths assigned to the horizontal edges,
then G has a rectilinear planar drawing realizing these angles and edge lengths if
and only if every cycle has a rectilinear planar drawing realizing the angles and
lengths. Furthermore, we can combine any embedding choices for the faces that
involve different vertical visibilities, so long as every vertical edge has the same
length in its two cycles.
2 Definitions
Following previous works in this area [10, 23] we formalize the notion of a flat
folding using self-touching configurations . Intuitively, these are planar embed-
dings in which edges and vertices are allowed to be infinitesimally close to each
other. A one-dimensional self-touching configuration of a graph G consists of a
mapping from G to a path graph H that maps vertices of G to vertices of H
and edges of G to paths in H , together with a magnified view of each vertex and
edge of H that describes the local connectivity of the image of G at that point.
In a self-touching configuration, the multiplicity of an edge in H is a positive
integer, the number of different edges of G that map to it. The magnified view of
an edge gives a linear ordering of the edges in its preimage. The magnified view
of a vertex v of H is a planar embedding of a neighborhood of the preimage of
v into a disk, consistent with the magnified views of the edges incident to v .
By replacing each vertex of H by its magnified view, and each edge of H
by a corridor of finite width through which each edge passes, it is possible to
transform a self-touching configuration into a conventional planar drawing (with
edges that may curve or bend) of the given graph G . We call this the expanded
drawing of a self-touching configuration (Figure 6).
We may now define a flat folding to be a self-touching configuration in which
all edges of H lie on a single line. We consider two flat foldings to be equivalent if
they have the same magnified views in the same order or in the reversed order as
 
Search WWH ::




Custom Search