Information Technology Reference
In-Depth Information
The Importance of Being Proper
(In Clustered-Level Planarity and
T
-Level Planarity)
Patrizio Angelini
1
, Giordano Da Lozzo
1
,Giuseppe Di Battista
1
,
Fabrizio Frati
2
, and Vincenzo Roselli
1
1
Department of Engineering, Roma Tre University, Italy
{
angelini,dalozzo,gdb,roselli
}
@dia.uniroma3.it
2
School of Information Technologies, The University of Sydney, Australia
fabrizio.frati@sydney.edu.au
Abstract.
In this paper we study two problems related to the drawing of level
graphs, that is,
T
-L
EVEL
P
LANARITY
and C
LUSTERED
-L
EVEL
P
LANARITY
.
We show that both problems are
NP
-complete in the general case and that they
become polynomial-time solvable when restricted to proper instances.
1 Introduction and Overview
Alevelgraph is
proper
if every of its edges spans just two consecutive levels. Several
papers dealing with the construction of level drawingsoflevelgraphs assume that the
input graph is proper. Otherwise, they suggest to make it proper by “simply adding
dummy vertices” along the edges spanning more than two levels. In this paper we show
that this apparently innocent augmentation has dramatic consequences if, instead of
constructing just a level drawing, we are also interested in representing additional con-
straints, like a clustering of the vertices or consecutivity constraints on the orderingsof
the vertices along the levels.
A
level graph
G
=(
V,E,ʳ
) is a graph with a function
ʳ
:
V
ₒ{
1
,
2
, ..., k
}
,
≤
k
≤|
V
|
such that
ʳ
(
u
)
=
ʳ
(
v
) for each edge (
u,v
)
∈
E
.Theset
V
i
=
with 1
{v|ʳ
(
v
)=
i}
is the
i
-th
level
of
G
.Alevelgraph
G
=(
V,E,ʳ
) is
proper
if for every
edge (
u,v
)
∈ E
, it holds
ʳ
(
u
)=
ʳ
(
v
)
±
1.A
level planardrawing
of (
V,E,ʳ
) maps
each vertex
v
of each level
V
i
to a point on the line
y
=
i
, denoted by
L
i
, and each
edgetoa
y
-monotone curve between its endpoints so that no two edges intersect. A
level graph is
level planar
if it admits a level planar drawing. A linear-time algorithm
for testing level planarity was presented by Junger
et al.
in [10].
A
clustered-level graph
(
cl-graph
) (
V,E,ʳ,T
) is a level graph (
V,E,ʳ
) equipped
with a
cluster hierarchy
T
, that is, a rooted tree where each leaf is an element of
V
and each internal node
μ
, called
cluster
, represents the subset
V
μ
of
V
composed of
the leaves of the subtree of
T
rooted at
μ
.A
clustered-level planardrawing
(
cl-planar
drawing)of(
V,E,ʳ,T
) is a level planar drawing of level graph (
V,E,ʳ
) together
with a representation of each cluster
μ
as a simple closed region enclosing all and
only the vertices in
V
μ
such that: (1) no edge intersects the boundary of a cluster more
than once; (2) no two cluster boundaries intersect; and (3) the intersection of
L
i
with
any cluster
μ
is a straight-line segment, that is, the vertices of
V
i
that belong to
μ
are
consecutive along
L
i
.Acl-graph is
clustered-level planar
(
cl-planar
) if it admits a cl-
planar drawing.C
LUSTERED
-L
EVEL
P
LANARITY
(CL-P
LANARITY
) is the problem
