Information Technology Reference
In-Depth Information
The hard direction in the proof of Lemma 2 is covered by the following result
from an earlier paper on the independent odd crossing number [19]. We call an
edge
e
in a drawing
D independently even
if it crosses every edge independent of
it an even number of times. More formally,
i
D
(
e,f
)
≡
0mod2forevery
f
which
is independent of
e
.
Lemma 3 (Pelsmajer, Schaefer, Stefankoviˇc[19]).
If D is a drawing of
a graph G in the plane, then G has a drawing in which the independently even
edges of D are crossing-free and every pair of edges crosses at most once.
The proof of Lemma 3 is constructive in the sense that the new drawing of
G
can be found in polynomial time (there are no explicit time bounds in [19], but
a running time quadratic in
O
(
|
G
|
) seems achievable).
Proof (of Lemma 2).
Suppose
P
(
D,F
) is solvable, and fix a solution
x
e,v
∈
{
V
(
G
), for some initial drawing
D
of
G
.Construct
adrawing
D
from
D
by performing an (
e,v
)-move for every
e
0
,
1
}
,for
e
∈
E
(
G
)
,v
∈
∈
E
(
G
)and
v
∈
V
(
G
) for which
x
e,v
= 1. Pick
uv
∈
F
and let
st
∈
E
(
G
) be an arbitrary
edge independent of
uv
.Then
i
D
(
uv,st
)=
i
D
(
uv,st
)+
x
uv,s
+
x
uv,t
+
x
st,u
+
x
st,v
≡
0mod2
,
since
x
e,v
is a solution of the system
P
(
D,F
). Thus
uv
is independently even.
Since
uv
was arbitrary, all edges in
F
are independently even, and, by Lemma 3,
there is a drawing of
G
in which all edges of
F
are free of crossings, and every
pair of edges in
E
(
G
)
−F
crosses at most once. Temporarily replace each crossing
with a vertex, and take a planar straight-line embedding of the resulting graph.
In that drawing, all edges of
F
are straight-line, and (after turning crossings
into bends and perturbing them slightly), all remaining edges have at most
|
1 bends.
For the other direction, assume
G
has a drawing
D
in which all edges of
F
are free of crossings. By Lemma 1 we know that there is a set of (
e,v
)-moves so
that
E
(
G
)
−
F
|−
i
D
(
uv,st
)+
x
uv,s
+
x
uv,t
+
x
st,u
+
x
st,v
mod 2
for all pairs of independent edges
uv
,
st
i
D
(
uv,st
)
≡
∈
E
(
G
). Now if
uv
∈
F
,then
i
D
(
uv,st
)=
0 for every edge
st
∈
E
(
G
). In particular,
i
D
(
uv,st
)+
x
uv,s
+
x
uv,t
+
x
st,u
+
x
st,v
≡
i
D
(
uv,st
)
≡
0mod2
,
so
x
e,v
is a solution to
P
(
D,F
), which is what we had to show.
3 Geometric Partial 1-Planarity
In the straight-line version of the partial planarity problem, we ask whether for a
given
G
and
F
E
(
G
), there is a straight-line drawing of
G
in which the edges
of
F
are free of crossings. We cannot settle the complexity of this problem, but
ↆ
