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
|
Search WWH ::




Custom Search