Information Technology Reference
In-Depth Information
from above and from below (a
vertical
pipe both from left and from right), then
we conclude that instance
I
is negative. Otherwise, if
w
exits
P
from (
i
) above, we set
y
t
(
P
)=
y
t
(
w
); (
ii
) below, we set
y
b
(
P
)=
y
b
(
w
); (
iii
) left, we set
x
l
(
P
)=
x
l
(
w
);or
(
iv
) right, we set
x
r
(
P
)=
x
r
(
w
).SeeFig.3(a).
Procedure
P
IPE
S
IDE
C
HECKER
:
Consider a
horizontal
(
vertical
)pipe
P
(
u,v
) and a vertex
w
exiting
P
(
u,v
) both throughvertex
u
and throughvertex
v
.If
u
and
v
are incident to
vertical
(
horizontal
) pipes, either
P
(
u,u
) and
P
(
v
,v
),
or
P
(
u
,u
) and
P
(
v,v
), respectively, then we conclude that instance
I
is negative.
Procedure
P
IPE
I
NTERLEAVE
C
HECKER
:
Suppose that there exist two
horizon-
tal
(
vertical
)pipes
P
(
u,v
) and
P
(
w,z
) such that
v
and
P
(
w,z
) haveaVP-
overlap, and
w
and
P
(
u,v
) have a VP-overlap. If either
v
is incident to a
verti-
cal
(
horizontal
)pipe
P
(
v,v
) and
w
is incident to a
vertical
(
horizontal
)
pipe
P
(
w,w
),or
v
is incident to a
vertical
(
horizontal
)pipe
P
(
v
,v
) and
w
is incident to a
vertical
(
horizontal
)pipe
P
(
w
,w
), then we conclude that
instance
I
is negative. See Fig.3(c).
If none of the above procedures can be applied, then we conclude that
I
is a positive
instance.
Theorem 1.
Let
I
=
G, ʱ, ʴ
be an instance of
AGD
-
L
∞
-
R
such that
G
is con-
nected. Algorithm
Algo-AGD-
L
∞
-
R
decides in polynomialtime whether
G, ʱ, ʴ
admits an anchored drawing.
Proof:
The initialization of the pipes and their refinement operated by procedure P
IPE
E-
QUALIZER
, both after the initialization and after each further modification, is trivially
necessary to meet the requirements that vertices are placed inside their regions and
edges are drawn as either horizontal or vertical segments.
Suppose that procedure P
IPE
C
HECKER
concluded that instance
I
is negative at some
point of the algorithm. If
x
r
(
P
)
<x
l
(
P
) (if
y
t
(
P
)
<y
b
(
P
)), then there exist two
vertical
(
horizontal
) pipes sharing a vertex that cannot be placed inside its re-
gion while drawing both its incident edges as rectilinear segments. Otherwise, there
exists a PP-overlap between two pipes
P
(
u,v
) and
P
(
w,z
) not overlapping with re-
gions
R
(
u
),
R
(
v
),
R
(
w
),and
R
(
z
). By Observation 2, the instance is negative.
We prove that the modifications operated by V
ERTEX
C
HECKER
,whenavertex
w
has a VP-overlap with a
horizontal
(
vertical
)pipe
P
(
u,v
) and
w
is incident to
a
vertical
(
horizontal
)
P
(
w,w
), do not restrict the possibility of constructing
an anchored drawing of
G, ʱ, ʴ
. Refer to Fig. 3(b). In fact, in this case, in any anchored
,edge (
w,w
) cannot traverse
P
(
u,v
) from top to bottom. As for
the fact that an instance in which
w
is incident to two
vertical
(
horizontal
)
pipes is correctly recognized as negative, observe that in this case one of the two vertical
edges incident to
w
necessarily crosses edge (
u,v
).
We prove that the modifications operated by P
IPE
B
LOCK
C
HECKER
,whenavertex
w
overlaps a pipe
P
(
u,v
) and does not exit through one of its vertices, do not restrict
the possibility of constructing an anchored drawing of
drawing of
G, ʱ, ʴ
.Suppose that
w
exits
P
(
u,v
) from below, the other cases being analogous. Refer to Fig. 3(a). The statement
G, ʱ, ʴ
