Information Technology Reference
In-Depth Information
we have a suggestive result for a generalized version. Suppose we are allowed
to specify sets
F
k
ↆ
E
(
G
), and ask whether
G
has a straight-line drawing in
which all edges in
F
k
have at most
k
crossings, for every
k
. The problem posed
by Angelini, Binucci, Da Lozzo, Didimo, Grilli, Montecchiani, Patrignani, and
Tollis [1] corresponds to specifying a set
F
0
of crossing-free edges. We will show
that if instead we specify a set
F
1
of edges that may be crossed at most once,
the problem has the same complexity as deciding the truth of statements in the
existential theory of the reals; in the terminology introduced in [24,20], it is
-
complete
. In analogy with the notion of 1-planarity (in which every edge may be
crossed at most once), we call the problem
geometric partial
1
-planarity
.
∃
R
Remark 1 (Equivalent Drawings).
Geometric 1-planarity was first studied by
Eggleton [8] and Thomassen [26], and more recently in [12], and several other
papers, but with one important difference: in these papers one is given an intial
1-planar drawing of
G
and asks whether there is an equivalent geometric 1-planar
drawing, where two drawings are
equivalent
if they have the same facial structure
(for this definition to make sense, we consider crossings to be vertices). With this
stronger notion, Thomassen [26] was able to identify forbidden subconfigurations,
which led to a linear-time testing algorithm [12]. Similarly, Nagamochi [18] shows
that if we are given a drawing of
G
and a 2-connected, spanning subgraph
S
of
G
, one can test in linear time whether there is an equivalent drawing of
G
in
which edges of
S
are free of crossings.
We will not give a formal definition of
∃
R
and
∃
R
-completeness (that can
be found in [24,20]), instead we will work with
STRETCHABILITY
,acomplete
problem for the class. This is just like working with
, the Boolean satisfiabil-
ity problem, (or any other
NP
-complete problem) rather than the formal class
NP
.
An
arrangement of pseudolines
in the plane is a collection of
x
-monotone
curves (that is, each pseudoline has exactly one crossing with every vertical
line) so that every pair of pseudolines crosses exactly once. An arrangement
of pseudolines is
stretchable
if all pseudolines can be replaced by straight lines
so that the order of crossings along the lines remains the same. See Figure 1
for an example of a pseudoline arrangement, and an equivalent straight-line
arrangement.
Mnev [17] showed that
SAT
, the problem of deciding whether
an arrangement of pseudolines is stretchable, is computationally equivalent to
deciding the truth of a sentence in the existential theory of the real numbers (for
an accessible treatment of Mnev's proof, see Shor [25]).
1
This led to the intro-
duction of the complexity class
STRETCHABILITY
∃
R
, which contains all problems which can be
translated in polynomial time to a sentence in the existential theory of the reals,
see [24,20] for more details. Similar to the theory of
NP
-completeness, there are
∃
R
-complete problems including stretchability, and truth in the existential the-
ory of the reals, but many other problems as well, such as the rectilinear crossing
1
Mnev actually showed a stronger result, his universality theorem, here we are only
interested in the computational aspects.
