Information Technology Reference
In-Depth Information
{
w
(
e,v
)
;(
e,v
)
∈
S
}
.Thealgorithm tests whether
0
∈
v
+
W
, which is equivalent to
Z
2
.
The difference between the original algorithm for planarity testing and ourversion
for
c
-planarity testing is the following. To keep the drawing of (
G, T
) clustered after
every deformation, for every edge
e
=
v
1
v
2
, we allow only those edge-vertex switches
(
e,v
) such that
v
is a child of some vertex of the shortest path between
v
1
and
v
2
in
T
.
We also include
edge-cluster switches
(
e,C
),where
C
is a child of some vertex of the
shortest path between
v
1
and
v
2
in
T
, that move
e
over all vertices of
C
simultaneously.
The corresponding vector
w
(
e,C
)
is the sumofall
w
(
e,v
)
for
v
the solvability of a system of linear equations over
C
. Therefore, the set
of allowed switches generates a subspace
W
c
of
W
.Ouralgorithm then tests whether
0
∈
v
+
W
c
.
Before running the algorithm, we first remove any loops and parallel edges and check
whether
∈
for the resultinggraph
G
.Thenwerunouralgorithm on
(
G
,T
). This means solving asystemof
O
(
E
(
G
)
V
(
G
)
|
|
<
3
|
|
E
(
G
)
V
(
G
)
2
) linear equa-
|
||
|
)=
O
(
|
V
(
G
)
|
E
(
G
)
2
)=
O
(
2
) variables. This can be performed in
O
(
2
ˉ
)
tions in
O
(
|
|
|
V
(
G
)
|
|
V
(
G
)
|
≤
4
.
752
) time using the algorithm by Ibarra, Moran and Hui[24].
O
(
|
V
(
G
)
|
3
Two Clusters
Let (
G, T
) be a two-clustered graph. Let
A
and
B
denote the two clusters of (
G, T
)
forming a partition of
V
=
V
(
G
).Forasubset
V
ↆ
V
,let
G
[
V
] denote the subgraph
of
G
induced by
V
.Bytheassumption of Theorem 1 and the strong Hanani-Tutte
theorem,
G
has an embedding. However, in this embedding,
G
[
B
] does not have to be
contained in a single face of
G
[
A
] and vice-versa. Hence, we cannot guarantee that a
clustered embedding of (
G, T
) exists so easily.
For an induced subgraph
H
of
G
,the
boundary
of
H
is the set of vertices in
H
that
have a neighbor in
G − H
. We say that an embedding
D
(
H
) of
H
is
exposed
if all
vertices from the boundary of
H
are incident to the outer face of
D
(
H
).
The following lemma is an easy consequence of the strong Hanani-Tutte theorem. It
helps us to find an exposed embedding of each connected component
X
of
G
[
A
] and
G
[
B
]. Later in the proof of Theorem 1 this allows us to remove non-essential parts of
each such component
X
and concentrate only on a subgraph
G
of
G
in which both
G
[
A
] and
G
[
B
] are outerplanar.
Lemma 1.
Suppose that
(
G, T
)
admits an independently even clustered drawing.Then
every connected componentof
G
[
A
]
∪
G
[
B
]
admits an exposed embedding.
Our proof of Theorem 1 proceeds by reducing the problem to an application of the
following lemma.
Lemma 2.
Let
(
G, T
)
denote a two-clustered bipartite graph inwhich thetwo non-
trivialclusters induce independentsets.If
G
admits an even drawing then
(
G, T
)
is
c-planar. Mo re over, there exists a clustered embedding of
(
G, T
)
with thesamerotation
systemasin the given even drawing of
G
.
