Information Technology Reference
In-Depth Information
We give an alternative polynomial time algorithm for deciding c-planarity of em-
bedded flat clustered graphs with small faces, reproving aresult of Di Battista and
Frati [11]. Ouralgorithm is based on the matroid intersection theorem. Its running time
is
O
(
3
.
5
) by [8], so it does not outperform the linear algorithm from [11], and
similarly as for ourotherresults we see its purpose more in mathematical foundations
than in giving an efficient algorithm. We find it quite surprising that by using completely
different techniques we obtained an algorithm for exactly the same case. Our approach
is very similar to a technique used [25] for deciding the global connectivity of switch
graphs.
|
V
(
G
)
|
Theorem 3.
[11]
Let
G
denote an embedded planar graph such that all its faces are
incidenttoat most five vertices. Let
(
G, T
)
denote a flatclustered graph.Wecan decide
in polynomialtime whether
(
G, T
)
admits a c-planarembedding,inwhich
G
keeps its
given embedding.
The rest of the paper is organized as follows. In Section 2 we describe an algorithm
for c-planarity testing of clustered graphs belonging to classes for which the correspond-
ing variant of the strong Hanani-Tutte theorem holds. In Section 3, we prove Theorem 1.
In Section 4 we prove Theorem 2. In Section 5 we prove Theorem 3. We conclude with
some remarks in Section 6.
2
Algorithm
Let (
G, T
) belong to a class of clustered graph for which the corresponding variant of
the strong Hanani-Tutte theorem holds, i.e., an independently even clustered drawing
of (
G, T
) implies that (
G, T
) is c-planar.
Ouralgorithm for c-planarity testing is an adaption of the algorithm for planarity test-
ing from [35, Section 1.4.2]. The algorithm tests whether we can continuously deform
a given clustered drawing
of (
G, T
) into an independently even clustered drawing
D
of (
G, T
). By the corresponding variant of the strong Hanani-Tutte theorem, the
existence of such a drawing is equivalent to c-planarity of (
G, T
).
During the deformation the parity of crossings between a pair of edges is affected
only when an edge
e
passes over a vertex
v
, in which case we change the parity of
crossingsof
e
with all the edges adjacent to
v
. We call such an event an
edge-vertex
switch
. Note that every edge-vertex switch can be performed independently of others,
for any initial drawing: we can always deform a given edge to pass close to a given
vertex, while introducing new crossingsonlyinpairs.Thus, for ourpurpose the contin-
uous deformation of
D
can be represented by a set
S
of edge-vertex switches. In
S
,an
edge-vertex switch of an edge
e
with a vertex
v
is represented as the ordered pair (
e,v
).
Adrawing of (
G, T
) can then be represented as a vector
v
D
2
,where
M
denotes
the number of unordered pairs of independent edges. The component of
v
correspond-
ing to a pair
∈
Z
is 1 if
e
and
f
cross an odd number of times and 0 otherwise. An
edge-vertex switch (
e,v
) is represented as a vector
w
(
e,v
)
∈
Z
{
e,f
}
2
such that its only
components equal to 1 are those indexed by pairs
where
f
is incident to
v
.The
set of all drawings that can be obtained from (
G, T
) by the switches from
S
then cor-
responds to an affine subspace
v
+
W
,where
W
is the subspace generated by the set
{
e,f
}
