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