Information Technology Reference
In-Depth Information
T
R
(
v
4
)
R
(
v
2
)
R
(
v
4
)
R
(
v
2
)
R
(
v
4
)
R
(
v
2
)
R
(
v
1
)
R
(
v
1
)
R
(
v
1
)
l
r
R
(
v
5
)
R
(
v
5
)
R
(
v
5
)
F
F
F
R
(
v
6
)
R
(
v
6
)
R
(
v
6
)
F
F
R
(
v
3
)
R
(
v
3
)
R
(
v
3
)
(a)
(b)
(c)
Fig. 7.
Clause for the reduction to the AGD-
L
2
-
S
problem. Vertices
v
1
,
v
2
,and
v
3
represent
the three literals of the clause. For readability, we show only pipes
P
(
v
1
,v
2
) and
P
(
v
5
,v
6
).
(a) Arrangement of the regions. (b) All literals are assigned
false
,andedges (
v
5
,v
6
) and
(
v
3
,v
4
) cross. The darker wedge represents all the possible positions for edge (
v
3
,v
4
) in this
truth assignment, which implies that the crossing is unavoidable. (c) Assigning
true
to any of
the literals allows for a planar drawing.
μ
1
,μ
2
,μ
3
The
split
gadget can be constructed by combining two turn gadgets
˄
L
=
, with
μ
1
=
μ
1
and where
˄
L
is obtained from
˄
R
by a vertical
mirroring.SeeFig.6(a).
The
not
gadget is constructed as follows. Consider two horizontally (vertically)
aligned variable gadgets
μ
1
and
μ
2
. Add an edge connecting
v
2
of
μ
1
to
v
1
of
μ
2
,
as in Fig.6(b).Place between
μ
1
and
μ
2
two pairs of adjacent vertices (
v
a
,v
b
) and
(
v
c
,v
d
) whose regions are placed in such a way that: (
i
) any drawing of edge (
v
a
,v
b
)
blocks the visibility between the true configurations of
μ
1
and
μ
2
; (
ii
) any drawing of
edge (
v
c
,v
d
) blocks the visibility between the false configurations of
μ
1
and
μ
2
;and
(
iii
) edges (
v
a
,v
b
) and (
v
c
,v
d
) can be drawn in such a way that there exists visibility
between different truth configurations of
μ
1
and
μ
2
. Hence, in any anchored drawing of
ʳ
, the configurations of
μ
1
and
μ
2
are different.
The
clause
gadget is constructed as follows. Refer to Fig. 7(a). Consider three ver-
tices
v
1
,
v
2
,and
v
3
whose regions are placed in such a way that their centers induce
a non-degenerated triangle
μ
1
,μ
2
,μ
3
and
˄
R
=
and the centers of
R
(
v
1
) and of
R
(
v
2
) lie on the same
horizontal line. These three vertices represent the three literals of the clause. While
R
(
v
2
) and
R
(
v
3
) maintain the usual convention to encode the truth value of the repre-
sented variable, for
R
(
v
1
) it is inverted. It can be easily realized by negating the value
of the variable. The gadget contains three more vertices:
v
4
,
v
5
,and
v
6
,andedges
(
v
1
,v
2
), (
v
2
,v
3
), (
v
1
,v
3
), (
v
3
,v
4
),and(
v
5
,v
6
). The center of
R
(
v
i
), with
i
=4
,
5
,
6,
lies inside
T
.Region
R
(
v
4
) is completely contained in pipe
P
(
v
1
,v
2
), except for an
arbitrarily small part ʠ, which lies inside
T
. Consider the two points
l
and
r
in which
the boundary of
R
(
v
4
) intersects
P
(
v
1
,v
2
). The boundary of
R
(
v
5
) is tangent to the
leftmost segment of the convex hull
H
of
T
R
(
v
3
).Region
R
(
v
6
) completely lies
to the right of the rightmost segment of
H
, except for an arbitrarily small part. Neither
R
(
v
5
) nor
R
(
v
6
) intersects
P
(
v
1
,v
2
).
If all the literals are set to
false
,then
v
4
must lie below edge (
v
1
,v
2
) (and hence in
ʠ). However, visibility between ʠ and
R
(
v
3
) is prevented by edge (
v
5
,v
6
) (Fig.7(b)).
{
l,r
}∪
