Information Technology Reference
In-Depth Information
for every pair of independent edges
uv,st
E
(
G
). Then
G
is planar if and only
if
P
(
D
) is solvable. The heart of the proof is showing that solvability of
P
(
D
)
leads to a planar drawing of
G
; we will not explain this part (see [21, Section 3]
for a detailed discussion). The other direction is a consequence of the following
well-known fact about drawings: as far as the crossing parity between pairs of
independent edges is concerned, one can turn any drawing of a graph into any
other drawing of the graph by performing a set of (
e,v
)-moves, where an (
e,v
)
-
move
consists of taking a small piece of
e
, moving it close to
v
and then pushing
it over
v
; the effect of an (
e,v
)-move is that the crossing parity between
e
and
any edge incident to
v
changes. Imagining one drawing of a graph morphing
into another, it is easy to believe that (
e,v
)-moves are sucient to get from one
drawing to another. We state this result without proof. For further details see [7,
Section 4.6] or [22, Lemma 1.12].
∈
Lemma 1.
If D and D
are two drawings of the same graph G, then there is a
set of
(
e,v
)
-moves so that
i
D
(
uv,st
)
≡
i
D
(
uv,st
)+
x
uv,s
+
x
uv,t
+
x
st,u
+
x
st,v
mod 2
,
for all edges uv, st
∈
E
(
G
)
,wherex
e,v
=1
if an
(
e,v
)
-move is performed, and
x
e,v
=0
otherwise.
E
(
G
), fix an arbitrary drawing
D
of
G
, and let
P
(
D,F
) be the following system of equations over GF(2):
For a graph
G
with a set of edges
F
ↆ
i
D
(
uv,st
)+
x
uv,s
+
x
uv,t
+
x
st,u
+
x
st,v
≡
0mod2
,
for every pair of independent edges
uv
∈
F
and
st
∈
E
(
G
).
Lemma 2.
G has a drawing ʓ in which F is free of crossings if and only if
P
(
D,F
)
is solvable.
Since the solvability of a linear system of equations over a field (in this case
GF(2)) can be decided in polynomial time, the following corollary is immediate.
Corollary 1.
Given a graph G with a set of edges F
E
(
G
)
, it can be decided
in polynomial time whether G has a drawing in which all edges in F are free of
crossings. In such a drawing we can assume that edges in F are straight-line,
and each edge in E
(
G
)
ↆ
−
F has at most
|
E
(
G
)
−
F
|−
1
bends.
The running time of the algorithm is on the order
O
((
nm
)
3
), where
n
=
|
V
(
G
)
|
and
m
=
, since systems of linear equations over a field can be solved in
cubic time, and
P
(
D,F
) can have as many as
O
(
nm
) equations and
O
(
nm
)
variables (note that we can assume that
|
E
(
G
)
|
=
O
(
n
): if the graph (
V
(
G
)
,F
)is
not planar, then there is no drawing of
G
in which all edges of
F
are free of
crossings; on the other hand, we cannot assume that
G
is planar). This may
seem impractical at a first glance, but recent experiments with an algorithm of
this type have been quite successful [11].
|
F
|
