Information Technology Reference
In-Depth Information
w
v
w
u
v
u
z
u
w
w
v
z
P
(
u, v
)
v
w
h
(a)
(b)
(c)
Fig. 3.
Vertices exiting pipes. (a) Vertex
w
exits
P
(
u,v
) from below. The cutof
P
(
u, v
) applied
by procedure P
IPE
B
LOCK
C
HECKER
is described by a dashed line. (b) Vertex
v
exits
P
(
w,z
)
through
w
.Thecutof
R
(
w
) and the consequent cutof
P
(
w,z
) appliedbyprocedure V
ERTEX
-
C
HECKER
is described by a dashed line. (c) A situation recognized by procedure P
IPE
I
NTER
-
LEAVE
C
HECKER
.
The general strategy of the main part of the algorithm is to progressively reduce the
size of the pipes. In particular, at each step we consider the current instance
I
i
and
modify it to obtain an instance
I
i
+1
with smaller pipes than
I
i
that admits an anchored
drawing if and only if
I
i
admits an anchored drawing.Eventually, such a process will
lead either to an instance
I
m
for which it is easy to construct an anchored drawing or to
conclude that instance
I
=
I
1
is negative.
Let
P
(
u,v
) be a
horizontal
pipe, and
w
be a vertex having aVP-overlap with
P
(
u,v
). Refer to Fig.3(a).Wesaythat
w
exits
P
from below
if there exists a vertex
h
such that: (
i
)
y
b
(
P
)
<y
b
(
w
)
<y
t
(
P
) and
x
r
(
u
)
<x
l
(
w
)
<x
r
(
w
)
<x
l
(
v
);
(
ii
)
y
t
(
h
)
<y
b
(
P
) and
x
r
(
u
)
<x
l
(
h
)
<x
r
(
h
)
<x
l
(
v
);and(
iii
) there exists a path
ʳ
=(
w,...,h
) in
G
connecting
w
to
h
in which every internal vertex
r
is such that
R
(
r
) intersects
P
. Symmetrically, we say that
w
exits
P
fromabove
if there exists a
vertex
h
with the same properties as before, except for the fact that
y
b
(
P
)
<y
t
(
w
)
<
y
t
(
P
),
y
b
(
h
)
>y
t
(
P
). Otherwise, we say that
w
exits
P
throughavertex
, either
u
or
v
.InFig. 3(b), vertex
v
exits pipe
P
(
w,z
) through
w
. Observe that, since
G
is
connected and no VV-overlap occurs in
I
, there always exists a path
ʳ
=(
w,...,h
) in
G
connecting
w
to a vertex
h
such that
h
does not have any VP-overlap with
P
; hence,
w
always exits
P
, either from above or below, or throughavertex.
Forthecaseofa
vertical
pipe
P
(
u,v
),weassume analogous definitions of ver-
tices exiting
P
from left, right
or
through a vertex
, either
u
or
v
.Aslong as one of the
following conditions is satisfied, we apply one of the procedures described hereunder.
Procedure
V
ERTEX
C
HECKER
:
Consider a vertex
w
having aVP-overlap with a
horizontal
(
vertical
)pipe
P
(
u,v
) such that
y
b
(
w
)
≤
y
b
(
P
)
<y
t
(
P
)
≤
y
t
(
w
)
(resp.,
x
l
(
w
)
x
r
(
w
)). If
w
is incident to two
vertical
(
hori-
zontal
) pipes, then we conclude that instance
I
is negative. Otherwise, if
w
is incident
to a
vertical
(
horizontal
)pipe
P
(
w,w
),thenset
y
b
(
w
)=
max
(
y
b
(
w
)
,y
b
(
P
))
(set
x
l
(
w
)=
max
(
x
l
(
w
)
,x
l
(
P
)). See Fig.3(b).Analogously, if
w
is incident to a
vertical
(
horizontal
)pipe
P
(
w
,w
),thenset
y
t
(
w
)=
min
(
y
t
(
w
)
,y
t
(
P
) (set
x
r
(
w
)=
min
(
x
r
(
w
)
,x
r
(
P
)).
≤
x
l
(
P
)
<x
r
(
P
)
≤
Procedure
P
IPE
B
LOCK
C
HECKER
:
Consider a pipe
P
(
u,v
) having aVP-overlap
with a vertex
w
such that
w
does not exit throughavertex.If
w
exits
P
(
u,v
) both
