Information Technology Reference
In-Depth Information
Advances on Testing C-Planarity
of Embedded Flat Clustered Graphs
Markus Chimani
1
,Giuseppe Di Battista
2
, Fabrizio Frati
3
, and Karsten Klein
3
1
Theoretical Computer Science, University Osnabr uck, Germany
markus.chimani@uni-osnabrueck.de
2
Dipartimento di Ingegneria, University Roma Tre, Italy
gdb@dia.uniroma3.it
3
School of Information Technologies, The University of Sydney, Australia
{
fabrizio.frati,karsten.klein
}
@sydney.edu.au
Abstract.
We show a polynomial-time algorithm for testing
c
-planarity of em-
bedded flat clustered graphs with at most two vertices per cluster on each face.
1
Introduction
A
clustered graph
C
(
G, T
) consists of a graph
G
(
V,E
), called
underlying graph
,and
of a rooted tree
T
, called
inclusion tree
, representing acluster hierarchy on
V
.The
vertices in
V
are the leaves of
T
, and the inner nodes of
T
, except for the root, are called
clusters
. The vertices that are descendants of a cluster
ʱ
in
T
belong to
ʱ
or
are in
ʱ
.A
c
-planardrawing
of
C
is a planar drawing of
G
together with a representation of each
cluster
ʱ
as a simple connected region
R
ʱ
enclosing all and only the vertices that are in
ʱ
;further, the boundaries of no two such regions
R
ʱ
and
R
ʲ
intersect; finally, only the
edges connecting vertices in
ʱ
to vertices not in
ʱ
cross the boundary of
R
ʱ
, and each
does so only once. A clustered graph is
c
-planar
if it admits a
c
-planar drawing.
Clustered graphs find numerous applications in computer science [22], thus theoreti-
cal questions on clustered graphs have been deeply investigated. From the visualization
perspective, the most intriguing question is to determine the complexity of testing
c
-
planarity of clustered graphs. Unlike for other planarity variants [21], like
upward pla-
narity
[14] and
partialembedding planarity
[1], the complexity of testing
c
-planarity
remains unknown since the problem was posed nearly two decades ago[13].
Polynomial-time algorithms to test the
c
-planarity of a clustered graph
C
are known
if
C
belongs to special classes of clustered graphs [7-11, 13, 15, 16, 18, 19], including
c
-
connected clustered graphs
,thatareclustered graphs
C
(
G, T
) in which, for each cluster
ʱ
,thesubgraph
G
[
ʱ
] of
G
induced by the vertices in
ʱ
is connected [8,10,13]. Effective
ILP formulations and FPTalgorithms for testing
c
-planarity have been presented [5, 6].
Generalizations of the
c
-planarity testing problem have also been considered [2, 12].
An important variant of the
c
-planarity testing problem is the one in which the clus-
tered graph
C
(
G, T
) is
flat
and
embedded
.Thatis,everycluster is a child of the root of
T
and a planar embedding for
G
(an order of the edges incident to each vertex) is fixed
Research partially supported by the Australian Research Council (grant DE140100708).
