Information Technology Reference
In-Depth Information
already in [28]. Since then an efficient algorithm for c-planarity testing or embedding
has been discovered only in some special cases. The general problem whether the c-
planarity of a clustered graph can be tested in polynomial time is wide open, already
when we restrict ourselves to three pairwise disjoint clusters and the case when the
embedding of
G
is a part of the input!
Aclustered graph (
G, T
) is
c-connected
if every cluster of (
G, T
) induces a con-
nected subgraph. In order to test a c-connected clustered graph (
G, T
) for c-planarity, it
is enough to test whether there exists an embedding of
G
in which for every
ʽ
∈
V
(
T
)
all vertices
u
V
(
ʽ
) are drawn in a single face of the sub-
graph
G
(
ʽ
) [14]. Cortese et al. [6] gave a structural characterization of c-planarity for
c-connected clustered graphs and provided a linear-time algorithm. The extended ab-
stract of Gutwenger et al. [19] contains an efficient algorithm in a more general case
of
almost connected
clustered graphs, which can be also used in the case of two clus-
ters. Biedl [2] is usually credited for giving the first polynomial time algorithm for
c-planarity with two clusters, including the case of straight-line or
y
-monotone draw-
ing. An alternative approach to the problem is given in [22]. On the other hand, only
very little is known in the case of three clusters, where already clustered cycles are
non-trivial to test for c-planarity [7] in a polynomial time.
The Hanani-Tutte theorem [21,37] is a classical result that provides an algebraic
characterization of planarity with interesting (and not only algorithmic) consequences;
see Section 2. The (strong) Hanani-Tutte theorem says that a graph is planar as soon as
it can be drawn in the plane so that no pair of independent edges crosses an odd num-
ber of times. Moreover, its variant known as the weak Hanani-Tutte theorem [3,30,33]
states that if we have a drawing
∈
V
(
G
) such that
u
∈
of a graph
G
where every pair of edges cross an even
number of times then
G
has an embedding that preserves the cyclic order of edges at
vertices from
D
D
. Note that the weak variant does not directly follow from the strong
Hanani-Tutte theorem. For sub-cubic graphs, the weak variant implies the strong vari-
ant. Other variants of the Hanani-Tutte theorem were proved for surfaces of higher
genus[32,34],
x
-monotone drawings [17,31], partially embedded planar graphs, and
several special cases of simultaneously embedded planar graphs [36]. See [35] for a
(not too recent) survey on applications of the Hanani-Tutte theorem and related results.
We prove a variant of the Hanani-Tutte theorem for clustered graphs consisting only
of two non-trivial clusters forming a partition of the vertex set. Similarly, as in the case
of other variants of the Hanani-Tutte theorem, as a byproduct of ourresult, we im-
mediately obtain a polynomial-time algorithm based on linear algebra for c-planarity
testing in the corresponding case. The downside is that the running time of the algo-
rithm is in
O
(
2
ˉ
),where
O
(
n
ˉ
) is the complexity of multiplication of square
|
V
(
G
)
|
n
n
matrices; see Section 2. The best current algorithms for matrix multiplication
give
ˉ<
2
.
3729 [18,39]. This fact does not make our work less interesting, since the
purpose of ourresults lies more in theoretical foundations than in its immediate conse-
quences. Also the worst case running time analysis often gives an unfair perspective on
the performance of algebraic algorithms, e.g., the simplex method.
We remark that there exist more efficient algorithms for planarity testingusing the
Hanani-Tutte theorem such as the one in [9,10], which runs in linear time, see also [35,
Section 1.4.1]. Moreover, in the case of
x
-monotone drawingsacomputation study [4]
×
