Information Technology Reference
In-Depth Information
and no vertex
u
V
i
. Hence,
vertices
u
∗
and
v
∗
,andedge (
u
∗
,v
∗
), can be drawn in
ʓ
∗
entirely inside the region
representing
μ
in such a way that
u
∗
and
v
∗
lie along lines
L
i
and
L
i
+1
and there exists
no crossing between edge (
u
∗
,v
∗
) and any other edge.
This concludes the proof of the lemma.
∈
V
i
+1
∩
V
μ
exists that is connected to two vertices
v,w
∈
Lemma 3.
Let
(
V,E,ʳ,T
)
be a level-connected instance of
CL-P
LANARITY
.An
equivalent proper instance
(
V,E,ʳ,
)
of
T
-L
EVEL
P
LANARITY
whose size is lin-
earin thesizeof
(
V,E,ʳ,T
)
can be constructed in lineartime.
T
Proof:
We construct (
V,E,ʳ,
T
) from (
V,E,ʳ,T
) as follows. Initialize
T
=
∅
.
For
i
=1
,...,k
,addto
atree
T
i
that is the subtree of the cluster hierarchy
T
whose
leaves are all and only the vertices of level
V
i
. Note that the set of leaves of the trees in
T
T
corresponds to the vertex set
V
. Since each internal node of the trees in
T
has at least
two children, we have that the size of (
V,E,ʳ,
T
) is linear in the size of (
V,E,ʳ,T
).
Also, the construction of (
V,E,ʳ,
T
) can be easily performed in linear time.
We prove that (
V,E,ʳ,T
) is
-level planar if and only if (
V,E,ʳ,T
) is cl-planar.
Suppose that (
V,E,ʳ,T
) admits a
T
-level planar drawing
ʓ
∗
;weshowhowto
construct a cl-planar drawing
ʓ
of (
V,E,ʳ,T
). Initialize
ʓ
=
ʓ
∗
. Consider each
level
V
i
, with
i
=1
,...,k
. By construction, for each cluster
μ
T
∈
T
such that there
exists a vertex
v
∈
V
i
∩
V
μ
, there exists an internal node of tree
T
i
∈T
whose leaves
V
μ
.Since
ʓ
∗
is
are all and only the vertices of
V
i
∩
-level planar, such vertices appear
consecutively along
L
i
. Hence, in order to prove that
ʓ
is a cl-planar drawing,itsuffices
to prove that there exist no four vertices
u,v,w,z
such that (i)
u,v
T
∈
V
i
and
w,z
∈
V
j
,
with 1
=
ʽ
; and (iii)
u
appears before
v
on
L
i
and
w
appears after
z
on
L
j
,orviceversa.Suppose, for a contradiction, that
such four vertices exist. Note that, we can assume
j
=
i
≤
i<j
≤
k
; (ii)
u,w
∈
V
μ
and
v,z
∈
V
ʽ
, with
μ
1 withoutlossofgenerality,
as (
V,E,ʳ,T
) is level-connected. Assume that
u
appears before
v
along
L
i
and
w
appears after
z
along
L
j
, the other case being symmetric. Since
ʓ
∗
is
±
-level planar,
all the vertices of
V
μ
appear before all the vertices of
V
ʽ
along
L
i
and all the vertices
of
V
μ
appear after all the vertices of
V
ʽ
along
L
j
. Also, since (
V,E,ʳ,T
) is level-
connected, there exists at least an edge (
a, b
) such that
a
T
∈
V
i
∩
V
μ
and
b
∈
V
j
∩
V
μ
,
andanedge (
c, d
) such that
c
V
ʽ
.However,under the above
conditions, these two edges intersect in
ʓ
and in
ʓ
∗
, hence contradicting the hypothesis
that
ʓ
∗
is
∈
V
i
∩
V
ʽ
and
d
∈
V
j
∩
-level planar.
Suppose that (
V,E,ʳ,T
) admits a cl-planar drawing
ʓ
; we show how to construct
T
). Initialize
ʓ
∗
=
ʓ
. Consider each level
V
i
, with
i
=1
,...,k
. By construction, for each internal node
w
of tree
T
i
∈T
T
-level planar drawing
ʓ
∗
of (
V,E,ʳ,
T
a
,there
exists a cluster
μ ∈ T
such that the vertices of
V
i
∩ V
μ
are all and only the leaves of
the subtree of
T
i
rooted at
w
.Since
ʓ
is cl-planar, such vertices appear consecutively
along
L
i
. Hence,
ʓ
∗
is
T
-level planar.
We get the following.
4
)
-time algorithm that decides whether a proper
instance
(
V,E,ʳ,T
)
of
C
LUSTERED
-L
EVEL
P
LANARITY
is cl-planar.
Theorem 4.
There exists an
O
(
|
V
|