Information Technology Reference
In-Depth Information
A
once). We now show that the dual graph of
forces the facial structure of the
line arrangement to be unique.
Let
v
V
B
be an arbitrary vertex representing a face of the line arrange-
ment, and
e
an edge corresponding to some line in
∈
V
I
∪
. We show that
v
lies on
thesamesideof
e
(within the region bounded by the cycle
C
through
V
A
∪
A
V
B
)
A
, so the two line arrangements have to be equivalent. If
v
in both
A
and
∈
V
B
this is forced by the cycle
C
;if
v
V
I
, we argue as follows: let
s
and
t
be the
V
B
-vertices closest to
e
(along
C
) and on the same side of
e
as
v
. We claim
that there is an
st
-path of length
∈
1on
V
I
vertices that passes through
v
.
Clearly, any such path must have length at least
|A| −
1, so we only need to
argue that a path of this length exists. To see this, start at
s
.Since
v
is an inner
vertex,
s
and
v
do not lie in the same face of the line arrangement, hence there
must be an edge
f
corresponding to a line of
|A| −
so that
s
and
v
lie on opposite
sides of
f
. More strongly, there must be such an edge
f
which contributes to the
boundary of the cell
v
lies in (if the two vertices were on the same side of all
lines contributing to the boundary of the cell, they would have to be in the same
cell); in other words, there is a cell adjacent to the cell containing
v
(sharing
f
),
which is closer to
s
(note that
t
and
v
havetolieonthesamesideof
f
,since
otherwise
s
and
t
lie on the same side of both
e
and
f
, but then they cannot
both be closest to
e
). By induction we can now show that there are paths
sv
and
vt
containing at most
A
|A|−
1 edges together (since
e
need never be crossed). But
then the path
svt
in
G
A
on
|A|−
1 edges cannot cross
e
, since it has to cross all
|A| −
1 edges corresponding to pseudolines (other than
e
). Hence
v
lies on the
same side of
e
in both
A
.
A
and
A
is a straight-line arrangement equivalent to
Since
A
, we conclude that
A
is stretchable, which is what we had to show.
In contrast, geometric 1-planarity is only
NP
-complete. This follows from
two well-known results: 1-planarity is
NP
-complete [10,14,4], and geometric 1-
planarity can be tested in linear time if a rotation system is given [26,12].
Theorem 2 (Folklore).
Testing geometric
1
-planarity is
NP
-complete.
Proof.
The problem lies in
NP
, since we can guess the rotation system, and then
use the linear time algorithm from [12] to check whether there is an obstruction
to geometric 1-planarity with that rotation system. To see
NP
-hardness, we use
the
NP
-hardness of testing 1-planarity. If a graph
G
is 1-planar, then it has a
1-planar drawing in which each edge has at most one bend: simply apply Fary's
theorem to the graph obtained from
G
by replacing each crossing by a dummy
vertex. To avoid that crossings and bends occur at the same location, we replace
each edge in
G
with a path of length three to get a new graph
G
.Then
G
is
1-planar if and only if
G
has a geometric 1-planar embedding in which all edges
incident to the original vertices of
G
are free of crossings. And that we can easily
guarantee by identifying all of these edges with an edge of a
K
6
-gadget. Let
H
be this new graph. Then
G
is 1-planar if and only if
H
is geometrically 1-planar.
Therefore, geometric 1-planarity is
NP
-hard.
