Information Technology Reference
In-Depth Information
v
1
w
1
v
2
u
1
u
2
w
2
v
1
u
3
u
3
u
1
u
2
v
2
(a)
(b)
Fig. 4.
Construction of the drawing when none of the procedures can be applied. (a) Two maximal
horizontal paths (
u
1
,u
2
,u
3
) and (
v
1
,v
2
) whose pipes have the same
y
-coordinates. Path (
v
1
,v
2
)
is assigned a
y
-coordinate slightly larger than (
u
1
,u
2
,u
3
). (b) Three maximal horizontal paths
(
u
1
,u
2
,u
3
), (
v
1
,v
2
),and(
w
1
,w
2
)whose pipes have the same
y
-coordinates. Path (
v
1
,v
2
) is
assigned a
y
-coordinate slightly larger than (
w
1
,w
2
).
follows from the fact that, in any anchored drawing of
, the drawing of path
ʳ
=(
w,...,h
) blocks visibility from
R
(
u
) to
R
(
v
) inside
P
(
u,v
) at least for all the
y
-coordinates in the range between the point where
w
is placed and the point where
h
is placed. Since
y
t
(
h
)
<y
b
(
P
), the point where
w
is placed determines a new lower
bound for the valueof
y
b
(
P
).Sincesuch a point cannot be below
y
b
(
w
), the statement
follows. As for the fact that an instance containing avertex
w
that exits a
horizon-
tal
pipe both from above and from below (a
vertical
pipe both from left and from
right) is correctly recognized as negative, observe that in this case the two paths starting
from
w
completely block visibility between from
R
(
u
) to
R
(
v
) inside
P
(
u,v
).
We prove that an instance containing avertex
w
that exits
P
(
u,v
) through both of
its vertices, and such that
u
and
v
are also incident to pipes
P
(
u,u
) and
P
(
v
,v
),
or vice versa, reaching them from different sides, is correctly recognized as negative
by procedure P
IPE
S
IDE
C
HECKER
. Namely, observe that in this case path (
u
,u,v,v
)
necessarily crosses one of the two paths starting from
w
.
Finally, suppose that procedure P
IPE
I
NTERLEAVE
C
HECKER
concluded that instance
I
is negative. Refer to Fig. 3(c). It is easy to observe that the fact that
v
and
w
are reached
from the same side is not compatible with an anchored drawing of
G, ʱ, ʴ
.
We conclude the proof of the theorem by showing that, when none of the described
procedures can be applied, it is always possible to draw every edge (
u,v
) inside its pipe
P
(
u,v
), as follows.
Consider every maximal horizontal path (
u
1
,...,u
r
). Note that, each vertex
u
i
, with
G, ʱ, ʴ
r
, is incident to at least a
vertical
pipe, either (
u
i
,u
i
) or (
u
i
,u
i
),asother-
wise edges (
u
i−
1
,u
i
) and (
u
i
,u
i
+1
) would have been replaced with edge (
u
i−
1
,u
i
+1
).
If all the vertices
u
i
are incident to a
vertical
(
u
i
,u
i
), then assign
y
-coordinate
equal to
y
t
(
u
i
) to
u
i
,for
i
=1
,...,r
; if all the vertices
u
i
are incident to a
vertical
(
u
i
,u
i
), then assign
y
-coordinate equal to
y
b
(
u
i
) to
u
i
,for
i
=1
,...,r
; finally, if there
exists at least a vertex
u
i
incident to a
vertical
(
u
i
,u
i
) and at least a vertex
u
j
in-
cident to a
vertical
(
u
j
,u
j
), then assign
y
-coordinate equal to
y
b
(
u
i
)+
y
t
(
u
i
2
to
u
i
,
for
i
=1
,...,r
. Assign
x
-coordinates to vertices of every maximal vertical path equal
to
x
l
(
u
i
),to
x
r
(
u
i
),orto
x
l
(
u
i
)+
x
r
(
u
i
2
,inananalogousway.
With a straightforward case analysis, it is possible to observe that, since none of
the conditions activating the described procedures is satisfied, there exists no cross-
ing in the drawing, apart from possible overlaps between edges belonging to different
1
≤
i
≤
