Information Technology Reference
In-Depth Information
R
-complete, it is sucient
to show that stretchability can be reduced to partial geometric 1-planarity to
establish
Since stretchability of pseudoline arrangements is
R
A
be an arbitrary
arrangement of pseudolines. We construct a graph G A and a set of edges F
-hardness of partial geometric 1-planarity. Let
G A
so that
is stretchable if and only if G A has a straight-line drawing in which
every edge in F has at most one crossing.
Let R be a parabola-shaped region (boundary of the form y = x 2 + c for
some constant c
A
lie within the
region R .Let V A be the intersection points of pseudolines with the parabolic
boundary of R (we can assume that all crossings of pseudolines lie in the convex
hull of V 1 ). The region R is separated by
R
) so that all crossings of pseudolines in
A
into faces, some of them adjacent
to the boundary of R , and some of them inner faces of the arrangement. We
choose a set of vertices V I consisting of an interior vertex for each inner face of
the arrangement; for each face on the boundary of R , we pick a vertex on the
interior of a boundary arc of the face, let V B of those boundary vertices; note
that all faces except the infinite face, are incident to a unique boundary arc; the
infinite face is incident to two boundary arcs, of which we pick one arbitrarily
to place the V B -vertex. Finally, pick a vertex p below R so that p can see all
vertices of V A
A
V B ; that is, a straight-line segment between p and any vertex in
V A
.
For every two vertices in V A belonging to the same pseudoline, add an edge
between those vertices. Add a frame as follows: connect the vertices of V A
V B does not cross the boundary of R .Let V = V A
V R
V I ∪{
p
}
V B
by a cycle that respects the order of those vertices along the boundary of R ,and
connect p to every vertex in V A
V B by an edge. Identify each edge of the frame
with an edge in a (new) K 6 . Finally, add the dual graph of the line arrangement
to V I
V B .Let F consist of all edges, except for the edges corresponding to the
original pseudolines. See Figure 2 for an example.
We first note that if A is stretchable, then G A has a straight-line drawing in
which every edge of F has at most one crossing. To see this, start with a straight-
line realization of A . Perform the construction of G A as we described it above.
Because of the convexity of R , we can draw the edges of the cycle on V A
V B
as well as the straight-line edges to p . We can then add a straight-line drawing
of each K 6 gadget to the frame so that the shared edge is free of crossings (and
the remainder of K 6 does not participate in unnecessary crossings). Finally, the
dual graph of the line arrangement can be added to V I
V B since any edge
connects two vertices in adjacent faces of the line arrangement which is always
possible with a straight-line arrangement, unless the resulting edge coincides
with the boundary of a cell. This cannot occur, however, since V I vertices lie
in the interior of faces, and the V B vertices lie on the boundary of the convex
region R . In this drawing, every edge in F has at most one crossing. Only edges
corresponding to the original pseudolines are crossed more than once by dual
edges.
For the other direction, start with a straight-line drawing of G A in which all
edges in F have at most one crossing. Suppose f is an edge of the frame and
let e be another edge in G A which does not belong to f 's K 6 gadget. If e and
 
Search WWH ::




Custom Search