Information Technology Reference
In-Depth Information
in advance; then, the
c
-planarity testing problem asks whether a
c
-planar drawing exists
in which
G
has the prescribed planar embedding. This setting can be highly regarded
for several reasons. First, several NP-hard graph drawing problems are polynomial-
time solvable in the fixed embedding scenario, e.g.,
upward planarity testing
[3, 14]
and
bend minimization in orthogonaldrawings
[14, 23]. Second, testing
c
-planarity of
embedded flat clustered graphs generalizes testing
c
-planarity of triconnected flat clus-
tered graphs. Third, testing
c
-planarity of embedded flat clustered graphs is strongly
related to a seemingly different problem, that we call
planarsetofspanning trees in
topological multigraphs
(
PSSTTM
): Given a non-planar topological multigraph
A
with
k
connected components
A
1
,...,A
k
, do spanning trees
S
1
,...,S
k
of
A
1
,...,A
k
exist
such that no two edges in
i
S
i
cross? Starting from an embedded flat clustered graph
C
(
G, T
), an instance
A
of the
PSSTTM
problem can be constructed that admits a solu-
tion if and only if
C
(
G, T
) is
c
-planar:
A
is composed of the edges that can be inserted
inside the faces of
G
between vertices of the same cluster, where each cluster defines a
multigraph
A
i
.The
PSSTTM
problem is NP-hard, even if
k
=1[20].
Testing
c
-planarity of an embedded flat clustered graph
C
(
G, T
) is a polynomial-
time solvable problem if
G
has no face with more than five vertices and, more in general,
if
C
is a
single-conflict
clustered graph [11], i.e., the instance
A
of the
PSSTTM
problem
associated with
C
is such that each edge has at most one crossing. A polynomial-time
algorithm is also known for testing
c
-planarity of embedded flat clustered graphs such
that the graph induced by each cluster has at most two connected components [17].
Finally, the
c
-planarity of clustered cycles with at most three clusters [9] or with each
cluster containing at most three vertices [19] can be tested in polynomial time.
Our Contribution.
In this paper we show how to test
c
-planarity in polynomial time
for embedded flat clustered graphs
C
(
G, T
) such that at most two vertices of each clus-
ter are incident to any face of
G
. While this setting might seem unnatural at a first
glance, its studyledtoadeep(inour opinion) exploration of some combinatorial prop-
erties of highly non-planar topological graphs. Namely, every instance
A
of the
PSSTTM
problem arising from our setting is such that there exists no sequence
e
1
,e
2
,...,e
h
of
edges in
A
with
e
1
and
e
h
in the same connected component of
A
and with
e
i
crossing
e
i
+1
,forevery1
≤
i
≤
h
−
1; these instances might contain a quadratic number of
crossings, which is not the case for single-conflict clustered graphs [11]. Within our
setting, performing all the “trivial local” tests and simplifications results in the rise of
nice global structures, called
ʱ
-donuts
, whose study was interesting to us.
Refer to the full version of the paper [4] for complete proofs.
2
Saturators, Con-Edges, and Spanning Trees
Anatural approach to test
c
-planarity of a clustered graph
C
(
G
(
V,E
)
,T
) is to search
for a
saturator
for
C
.Aset
S
V
is a saturator for
C
if
C
(
G
(
V,E
S
)
,T
) is
a
c
-connected
c
-planar clustered graph. Determining the existence of a saturator for
C
is equivalent to testing the
c
-planarity of
C
[13]. Thus, the core of the problem consists
of determining
S
so that
G
[
ʱ
] is connected, for each
ʱ
ↆ
V
×
∪
T
,andsothat
G
is planar.
For embedded flat clustered graphs (see Fig. 1(a)), the problem of finding saturators
∈
