Information Technology Reference
In-Depth Information
t i− 1
t i
t i +1
y
C
T i− 1
T i
T i +1
T i +1
L i +1
T i
L i
u
z
T i− 1
T
T 1
L i− 1
P i− 1
Q i− 1
P i
Q i
P i +1
Q i +1
x
p i− 1
q i− 1
p i
q i
p i +1
q i +1
(a)
(b)
Fig. 3. Illustration for the proof of Lemma 1. Index i is assumed to be even. (a) A T -level planar
drawing ʓ of instance ( V,E,γ,T ). (b) The SEFE ʓ 1 , ʓ 2 of instance G 1 , G 2 of SEFE-2
corresponding to ʓ . Correspondence between a vertex u ∈ V i and leaves u ( T i ) ∈ T i , u ( P i )
P i ,and u ( Q i ) ∈ Q i is highlighted by representing all such vertices as white boxes.
or with q i , otherwise; also, for each edgein E connecting avertex u
V i with a vertex
V i− 1 , graph G 1 has an edge connecting the leaf u ( P i ) of P i corresponding to u
with the leaf v ( Q i− 1 ) of Q i− 1 corresponding to v (such leaves exist by construction).
Suppose that i is odd. Then, graph G 1 has an edge between u ( T i ) and either u ( P i ),
if it exists, or p i ,otherwise.Graph G 2 contains G plus the following edges. For i =
1 ,...,k , consider each vertex u
v
V i .Suppose that i is odd. Then, G 2 has an edge
connecting u ( T i ) with either the leaf u ( Q i ) of Q i corresponding to u , if it exists, or
with q i , otherwise; also, for each edgein E connecting avertex u
V i with a vertex
V i− 1 , graph G 2 has an edge ( u ( P i ) ,v ( Q i− 1 )).Suppose that i is even. Then, graph
G 2 has an edge between u ( T i ) and either u ( P i ), if it exists, or p i ,otherwise.
Graph G is clearly connected. We prove that G 1 and G 2 are 2-connected, that is,
removing any vertex v disconnects neither G 1
v
nor G 2 .If v is a leaf of T i , P i ,or Q i ,
k ,thenremoving v disconnects neither G 1 nor G 2 ,since G remains
connected. If v is an internal node (the root) of T i , P i ,or Q i ,sayof T i , with 1 ≤ i ≤ k ,
then removing v disconnects G into one component T i ( v ) containing all the vertices
of
i
with 1
, except for v ) and into some subtrees T i,j of T i rooted the
children of v ; however, by construction, each leaf u ( T i ) of T i,j is connected to T i ( v ) via
an edgeof G 1 , namely either ( u ( T i ) ,u ( P i )), ( u ( T i ) ,p i ), ( u ( T i ) ,u ( Q i )),or( u ( T i ) ,q i )
(and similar for G 2 ), hence G 1 (and G 2 ) is connected after the removal of v .
Observe that, if ( V,E,ʳ,
C
(resp. all the vertices of
C
T
) has n T
nodes in the trees of
T
(where
|
V
|
<n T ), then
G 1 , G 2
G 1 , G 2
contains at most 3 n T
vertices. Also, the number of edges of
is at
G 1 , G 2
most
|
E
|
+2 n T . Hence, the size of
is linear in the size of ( V,E,ʳ,
T
);also,
G 1 , G 2
it is easy to see that
can be constructed in linear time.
G 1 , G 2
We prove that
admits a SEFE if and only if ( V,E,ʳ,
T
) is
T
-level planar.
G 1 , G 2
ʓ 1 , ʓ 2
Suppose that
admits a SEFE
. We show how to construct a draw-
ing ʓ of ( V,E,ʳ,
k ,let ʘ ( T i ) be the order in which the leaves of T i
appear in a pre-order traversal of T i in
T
).For1
i
ʓ 1 , ʓ 2
O i of the vertices
of V i along L i be either ʘ ( T i ),if i is odd, or the reverse of ʘ ( T i ),if i is even.
We prove that ʓ is
; then, let the ordering
T
-level planar. For each i =1 ,...,k ,
O i is compatible with
ʓ 1 , ʓ 2
T i ∈T
, since the drawing of T i , that belongsto G ,isplanarin
.Suppose, for
 
Search WWH ::




Custom Search