Information Technology Reference
In-Depth Information
Fig. 1.
(Left)
A pseudoline arrangement.
(Right)
A straight-line arrangement equiva-
lent to the pseudoline arrangement on the left.
number (there is a wikipedia page, for example [28]). We note that
contains
NP
, since the existential theory of the real numbers easily encodes satisfiability,
and in turn
∃
R
∃
R
is contained in
PSPACE
, due to a famous result by Canny [5].
Therefore any
-complete problem, such as partial geometric 1-planarity is
NP
-hard, and can be solved in polynomial space.
∃
R
Theorem 1.
Partial Geometric
1
-Planarity is
∃
R
-complete.
In particular, we conclude that the problem is
NP
-hard, and lies in
PSPACE
.
For the proof we make use of a simple gadget.
Lemma 4.
There is no drawing of a K
6
and a vertex-disjoint cycle C so that
all edges in the K
6
have at most one crossing, and there is a crossing between
an edge of K
6
and the cycle.
Proof.
Suppose there were a drawing as described in the lemma, in which a
K
6
-
edge
e
=
uv
crosses a cycle edge
f
∈
E
(
C
). Then
e
cannot cross any of the edges
in
E
(
C
)
, since it has at most one crossing, and thus no edge incident to
u
can cross an edge incident to
v
: to have a common point, one of them would
have to cross
C
, but then it would have two crossings, one with the cycle, and
one with the other edge. Therefore, the edges adjacent to
e
do not cross each
other at all. This implies that the drawing of the
K
6
contains 4 triangles with a
shared edge
e
whose other edges do not cross each other. On the sphere, there
is only one such drawing: 4 nested triangles (with a common base). But this
implies that two of the endpoints of those triangles are separated by the other
two triangles, which means the original endpoints cannot be joined by an edge in
a 1-planar drawing of the
K
6
, since it would have to cross the other two triangles
(it cannot cross
e
,since
e
already has a crossing).
−{
f
}
Proof (of Theorem 1).
The problem can easily be expressed using an existentially
quantified statement over the real numbers: use the existential quantifiers to find
the locations of the vertices of the graph; once the vertices are located, it is easy
to express that each edge in
F
iscrossedatmostonce.Thisshowsthatthe
problem lies in
∃
R
.
