Information Technology Reference
In-Depth Information
a contradiction, that two edges (
u,v
)
,
(
w,z
)
∈
E
exist, with
u,w
∈
V
i
and
v,z
∈
V
i
+1
,
that intersect in
ʓ
. Hence, either
u
appears before
w
in
O
i
and
v
appears after
z
in
O
i
+1
, or vice versa. Since
i
and
i
+1have different parity, either
u
appears before
w
in
ʘ
(
T
i
) and
v
appears before
z
in
ʘ
(
T
i
+1
), or vice versa. We claim that, in both
cases, this implies a crossing in
ʓ
1
,
ʓ
2
between paths (
q
i
,u
(
Q
i
)
,v
(
P
i
+1
)
,p
i
+1
) and
G
1
,
G
2
(
q
i
,w
(
Q
i
)
,z
(
P
i
+1
)
,p
i
+1
) in
. Since the edges of these two paths belong all
to
G
1
or all to
G
2
, depending on whether
i
is even or odd, this yields a contradiction.
We now prove the claim. The pre-order traversal
ʘ
(
Q
i
) of
Q
i
(the pre-order traversal
ʘ
(
P
i
+1
) of
P
i
+1
)in
ʓ
1
,
ʓ
2
restricted to the leaves of
Q
i
(of
P
i
+1
) is the reverse of
ʘ
(
T
i
) (of
ʘ
(
T
i
+1
)) restricted to the vertices of
V
i
(of
V
i
+1
) corresponding to leaves
of
Q
i
(of
P
i
+1
). Namely, each leaf
x
(
Q
i
) of
Q
i
(
y
(
P
i
+1
) of
P
i
+1
) is connected to
leaf
x
(
T
i
) of
T
i
(
y
(
T
i
+1
) of
T
i
+1
)inthesamegraph, either
G
1
or
G
2
, by construction.
Hence, the fact that
u
appears before (after)
w
in
ʘ
(
T
i
) and
v
appears before (after)
z
in
ʘ
(
T
i
+1
) implies that
u
appears after (before)
w
in
ʘ
(
Q
i
) and
v
appears after (before)
z
in
ʘ
(
P
i
+1
). In both cases, this implies a crossing in
ʓ
1
,
ʓ
2
between the two paths.
Suppose that (
V,E,ʳ,
T
) admits a
T
-level planar drawing
ʓ
.Weshowhowto
ʓ
1
,
ʓ
2
G
1
,
G
2
construct a SEFE
of
.For1
≤
i
≤
k
,let
O
i
be the order of the
vertices of level
V
i
along
L
i
in
ʓ
.Since
ʓ
is
T
-level planar, there exists an embedding
ʓ
i
of tree
T
i
∈T
O
i
.If
i
is odd (even), then assign to each
internal vertex of
T
i
the same (resp. the opposite) rotation scheme as its corresponding
vertex in
ʓ
i
. Also, if
i
is odd, then assignto
p
i
(to
q
i
) the rotation scheme in
G
1
(resp.
in
G
2
)such that the paths that connect
p
i
(resp.
q
i
) to the leaves of
T
i
, either with an
edge or passing through a leaf of
P
i
(resp. of
Q
i
), appear in the same clockwise order as
the vertices of
V
i
appear in
that is compatible with
O
i
;if
i
is even, then assignto
p
i
(to
q
i
) the rotation scheme
in
G
2
(resp. in
G
1
)such that the paths that connect
p
i
(resp.
q
i
) to the leaves of
T
i
appear in the same counterclockwise order as the vertices of
V
i
appear in
O
i
. Finally,
consider the embedding
ʓ
i,i
+1
obtained by restricting
ʓ
to the vertices and edges of the
subgraph induced by the vertices of
V
i
and
V
i
+1
.If
i
is odd (even), then assigntothe
leaves of
Q
i
and
P
i
+1
in
G
1
(in
G
2
) the same rotation scheme as their corresponding
vertices have in
ʓ
i,i
+1
. This completes the construction of
ʓ
1
,
ʓ
2
.
ʓ
1
,
ʓ
2
G
1
,
G
2
. Since the rotation scheme of the
internal vertices of each
T
i
are constructed starting from an embedding of
ʓ
i
of tree
T
i
∈T
We prove that
is a SEFE of
O
i
, the drawing of
T
i
is planar. Further, since the
rotation schemes of
p
i
(of
q
i
) are also constructed starting from
that is compatible with
O
i
, there exists no
crossing between two paths connecting
t
i
and
p
i
(
t
i
and
q
i
), one passing through a leaf
u
(
T
i
) of
T
i
and, possibly, through a leaf
u
(
P
i
) of
P
i
(through a leaf
u
(
Q
i
) of
Q
i
), and
the other passing through a leaf
v
(
T
i
) of
T
i
and, possibly, through a leaf
v
(
P
i
) of
P
i
(through a leaf
v
(
Q
i
) of
Q
i
). Finally, since the rotation schemes of the leaves of
Q
i
and
P
i
+1
are constructed from the embedding
ʓ
i,i
+1
obtained by restricting
ʓ
to the
vertices and edges of the subgraph induced by the vertices of
V
i
and
V
i
+1
,thereexist
no two crossing edges between leaves of
Q
i
and
P
i
+1
.
We remark that a reduction from
T
-L
EVEL
P
LANARITY
to SEFE-2 was described
by Schaefer in [12]; however, the instances of SEFE-2 obtained from that reduction do
not satisfy any conditions that make SEFE-2 known to be solvable in polynomial-time.
