Information Technology Reference
In-Depth Information
R
(
v
1
)
R
(
v
1
)
R
(
v
3
)
R
(
v
3
)
R
(
v
4
)
R
(
v
4
)
R
(
v
2
)
R
(
v
2
)
(a)
(b)
(c)
(d)
Fig. 5.
Variable
gadget for the reduction to the AGD-
L
2
-
problem in its false (a) and true(b)
configurations. (c) Propagation of the true configuration of a variable gadget. (d)
Turn
gadget in
its false configuration.
S
R
(
v
c
)
R
(
v
a
)
R
(
v
d
)
R
(
v
b
)
(a)
(b)
Fig. 6.
(a)
Split
gadget in its true configuration. (b)
Not
gadget.
Theorem 2.
AGD
-
L
2
-
S
is NP-hard.
Proof:
To prove hardness we reduce problem P3SAT to AGD-
L
2
-
S
, under the hy-
pothesis that Property A is satisfied (no overlap among vertex regions).
Let
ˆ
be an instance of P3SAT with
n
variables and
m
clauses. We describe how to
construct an equivalent instance
ʳ
of AGD-
L
2
-
. For each variable
x
i
,
i
=1
,...,n
,
we create a
variable
gadget, whose two families of planar drawings are depicted in
Figs. 5(a) and 5(b), consisting of four vertices
v
1
,v
2
,v
3
,
and
v
4
and edges (
v
1
,v
2
)
and (
v
3
,v
4
).Theregions assigned to the vertices are placed as follows: (
i
) the centers
of
R
(
v
1
) and of
R
(
v
2
) lie on the same vertical line; (
ii
) the centers of
R
(
v
3
) and
of
R
(
v
4
) lie on the same horizontal line; (
iii
) pipe
P
(
v
1
,v
2
) has an intersection of
arbitrarily small area with both
R
(
v
3
) and
R
(
v
4
);and(
iv
) pipe
P
(
v
3
,v
4
) intersects
neither
R
(
v
1
) nor
R
(
v
2
). Hence, in any anchored drawing of
ʳ
,edge (
v
1
,v
2
) is drawn
either to the left of
v
3
(as in Fig. 5(a)) or to the right of
v
4
(as in Fig. 5(b)). In both cases,
edge (
v
1
,v
2
) is drawn almost vertical. We call these two configurations
false
and
true
configurations for the variable gadget, respectively, and associate them with the
false
and
true
values for the corresponding variable
x
i
.Thetruth value of a variable can be
propagated by concatenating asequence of variable gadgets
μ
1
,...,μ
k
in which
R
(
v
1
)
of
μ
i
is identified with
R
(
v
2
) of
μ
i
+1
, for each
i
=1
,...,k
S
1.SeeFig.5(c).
The
turn
gadget can be constructed by concatenating three variable gadgets,
μ
1
,
μ
2
and
μ
3
, as depicted in Fig.5(d),insuch a way that
μ
2
has a clockwise rotation of 45
ⓦ
with respect to
μ
1
,and
μ
3
has a clockwise rotation of 90
ⓦ
with respect to
μ
1
.
−
