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