Information Technology Reference
In-Depth Information
showed that the Hanani-Tutte approach [17] performs really well in practice. This
should come as no surprise, since Hanani-Tutte theory seems to provide solid theo-
retical foundations for graph planarity that bringstogether its combinatorial, algebraic,
and computational aspects [36].
Notation.
In the present paper we assume that
G
=(
V,E
) is a (multi)graph. We use a
shorthand notation
G
E
),
respectively. The
rotation
at a vertex
v
is the clockwise cyclic order of the end pieces
of edges incident to
v
.The
rotation system
of a graph is the set of rotations at all its
vertices. We say that two embeddingsofagraph are the
same
if they have the same
rotation system up to switching the orientations of all the rotations simultaneously. We
say that a pair of edges in a graph are
independent
if they do not share a vertex. An edge
in a drawing is
even
if it crosses every other edgeanevennumber of times. A drawing
of a graph is
even
if all edges are even.
E
for (
V
−
v
and
G
∪
\{
v
}
,E
\{
vw
|
vw
∈
E
}
),and(
V,E
∪
Hanani-Tutte for Clustered Graphs.
Aclustered graph (
G, T
) is
two-clustered
if the
root of
T
has exactly two children and only leaves as grandchildren. In other words, a
two-clustered graph has exactly two non-trivial clusters, which form a partition of the
vertex set.
We extend the strong version of the Hanani-Tutte theorem as follows. A drawing of
a graph is
independently even
if every pair of independent edges in the drawing cross
an even number of times.
Theorem 1.
If a two-clustered graph
(
G, T
)
admits an independently even clustered
drawing then
(
G, T
)
is c-planar.
The weak variant of Theorem 1 is a special case of the result obtained recently by the
first author [15]. On the other hand, we exhibit examples of clustered graphs with more
than two disjoint clusters that are not c-planar, but admit an even clustered drawing.
Theorem 2.
Fo r every
r
3
there exists a flatclustered cycle with
r
clusters thatis
not c-planar and admits an even clustered drawing.
≥
Gutwenger et al. [20] recently showed that by using the reduction from [36] our
counter-examples can be turned into counter-examples for [36, Conjecture 1.2] and
for a variant of the Hanani-Tutte theorem for two simultaneously embedded planar
graphs [36, Conjecture 6.20]. Ourcounter-examples show that a straightforward ex-
tension of Theorem 1 or its weak variant to flat clustered graphs with more than two
clusters is not possible. Nevertheless, interesting extensions are still possible, e.g., in
the c-connected case, as shown in the full version of this extended abstract [16], or for
strip clustered graphs [15].
Aclustered graph (
G, T
) is
flat
if no non-root cluster of (
G, T
) has a non-trivial sub-
cluster; that is, if every root-leaf path in
T
has at most three vertices. A pair (
D
(
G
)
,T
) is
(
G
) is an embedding
of
G
in the plane, not necessarily a clustered embedding. The embedded clustered graph
(
an
embedded clustered graph
if (
G, T
) is a clustered graph and
D
(
G
)
,T
) is
c-planar
if it can be extended to a clustered embedding of (
G, T
),by
choosing a topological disc for each cluster.
D
