Information Technology Reference
In-Depth Information
Proof sketch.
The proof uses topological arguments to establish the following claim:
If
e
μ
/
S
, then the end-vertices of
e
μ
are on diffent sides of a cycle composed of con-
edges for
ʽ
that cannot be crossed by con-edges for
μ
in
S
, hence
S
does not connect
μ
, a contradiction.
∈
We now prove that our simplifications form a “complete set”.
Lemma 18.
Suppose that
S
IMPLIFICATIONS
1-8
do not apply to
A
andthat
T
ESTS
1-4
fail on
A
.Then,every con-edgein
A
crosses exactly onecon-edgein
A
.
Proof sketch.
Since S
IMPLIFICATIONS
2-3 do not apply to
A
, every con-edge crosses
at least one con-edge. Suppose, for a contradiction, that there exists a con-edgefora
cluster
ʱ
that has a conflict with at least two con-edges. Since S
IMPLIFICATIONS
1-4
do not apply to
A
and T
ESTS
1-4 fail on
A
, by Lemma 12 there exists an
ʱ
-donut
with spokes
e
ʱ
,...,e
ʱ
. If the conflicting structures of
e
ʱ
and
e
ʱ
are isomorphic, then
S
IMPLIFICATION
5 applies to
A
.Otherwise,if
k
3 and the conflicting structures of
e
ʱ
and
e
ʱ
are isomorphic (not isomorphic) when restricted to sets
H
0
(
e
j
ʱ
),
L
1
(
e
j
ʱ
),and
H
1
(
e
j
ʱ
),thenS
IMPLIFICATION
7 (resp. S
IMPLIFICATION
6) applies to
A
.If
k
=2
and the conflicting structures of
e
ʱ
and
e
ʱ
are not isomorphic, then S
IMPLIFICATION
8 applies to
A
. This provides a contradiction.
≥
A linear-time algorithm to determine whether a planar set
S
of spanning trees exists
for a single-conflict graph is known [11]. We thus finally get:
Theorem 1.
There exists an
O
(
3
)
-time algorithm to test the
c
-planarity of an em-
bedded flatclustered graph
C
withat most two vertices per cluster on each face.
Proof.
Multigraph
A
can be easily constructed in
O
(
|
C
|
2
) time, so that
A
has
O
(
)
vertices and edges and satisfies Property 1. By Lemma 2, it suffices to show how to
solve the
PSSTTM
problem for
A
in
O
(
|
C
|
|
C
|
3
) time. Algorithm 1 correctly determines
whether a planar set
S
of spanning trees for
A
exists, by Lemmata 3-18. It can be
easily tested in
O
(
|
C
|
2
) time whether the pre-conditions of each of S
IMPLIFICATIONS
1-8 and T
ESTS
1-4 are satisfied; also, the actual simplifications, that is, removing and
contracting edges in
A
, can be performed in
O
(
|
A
|
|
A
|
) time. Furthermore, the algorithm
in [11] runs in
O
(
|
A
|
) time. Since the number of performed tests and simplifications is
3
), and hence in
O
(
3
).
in
O
(
|
A
|
), the total running time is in
O
(
|
A
|
|
C
|
5
Conclusions
We presented a polynomial-time algorithm for testing
c
-planarity of embedded flat clus-
tered graphs with at most two vertices per cluster on each face. An interesting extension
of ourresults would be to devise an FPTalgorithm to test
c
-planarity of embedded flat
clustered graphs, where the parameter is the maximumnumber
k
of vertices of the same
cluster on any face. Several key lemmata (e.g. Lemmata 5 and 6) do not apply if
k>
2,
hence even an algorithm with running time
n
O
(
f
(
k
))
seems to be an elusive goal.
References
1. Angelini, P., Di Battista, G., Frati, F., Jelınek, V., Kratochvıl, J., Patrignani, M., Rutter, I.:
Testing planarity of partially embedded graphs. In: SODA 2010, pp. 202-221. ACM (2010)
