Information Technology Reference
In-Depth Information
maximal horizontal (vertical) paths whose pipes have the same bottom and top
y
-
coordinates (the same left and right
x
-coordinates). However, these overlaps can be
always eliminated by increasing (decreasing) of an arbitrarily small amount the coordi-
nates of the overlapping paths (see two examples in Fig. 4(a) and 4(b)), again duetothe
fact that none of the conditions activating the described procedures is satisfied.
4
Hardness Results
In this section we prove the hardness of the A
NCHORED
G
RAPH
D
RAWING
problem
in different settings. In particular, Theorem 2 is devoted to the hardness of the AGD-
L
2
-
problem, i.e., the problem of generating planar straight-line drawingsoftheinput
graph where the vertex regions are circles of radius
ʴ
. Theorem 3, instead, is devoted to
the hardness of the AGD-
L
2
-
S
problem, where the regions are circles of radius
ʴ
and
edges are required to be drawn as horizontal or vertical segments.
The proofs of hardness for the remaining variants of the problem listed in Table 1
can be derived from these two and, thus, will not be explained in detail. Namely, the re-
duction to AGD-
L
1
-
R
R
is very similar to that used for AGD-
L
2
-
R
, and can be obtained
by suitably replacing circles with diamond-shaped regions that ensure analogous geo-
metric visibility and obstruction properties. The same holds for the hardness proof of
AGD-
L
∞
-
S
, that can be obtained from AGD-
L
2
-
S
with small adaptations of the gad-
gets. Finally, the reduction to AGD-
L
1
-
where
all the geometric constructions are rotated by 45
o
, transforming the square-shaped re-
gions of AGD-
L
∞
-
S
is the same as the one for AGD-
L
∞
-
S
.
All our proofs are based on a reduction from the NP-complete problem P
LANAR
3-S
ATISFIABILITY
[8], defined as follows.
Problem:
P
LANAR
3-S
ATISFIABILITY
(P3SAT).
Instance:
A planar bipartite graph
G
=(
V
v
,V
c
,E
) where: (
i
)
V
v
is a set
of variables; (
ii
)
V
c
is a set of clauses, each consisting of exactly three literals repre-
senting variables in
V
v
;and(
iii
)
E
is a set of edges connecting each variable
v
S
into the diamond-shaped regions of AGD-
L
1
-
S
V
v
to all the clauses containing a literal representing
v
.
Question:
Does there exist a truth
assignment to the variables so that each clause has at least one
true
literal?
For each of our problems, we describe gadgets that, given an instance
ˆ
of P3SAT,
can be combined to construct an instance
ʳ
of the considered problem. Namely, we
describe a gadget for each of the following:
variable
,
not
,
turn
,
split
,and
clause
.
The variable gadget has two families of planar drawings, corresponding to the two
truth values. The not gadget admits planar drawings that invert its inputtruth value. The
turn gadget admits planar drawings that propagate its inputtruth value in a direction that
is orthogonal to the original one. The split gadget admits planar drawings that propagate
its inputtruth value to two different directions. Finally, the clause gadget is planar if and
only if at least one of its input literals is
true
.Thegadgets are combined following
the structure of a planar drawing of
ˆ
, so that any planar drawing of
ʳ
corresponds to
atruth assignment for the variables satisfying
ˆ
. Similarly, given a truth assignment
for the variables that satisfies
ˆ
,thegadgets for variables can be drawn accordingly to
obtain a planar drawing of
ʳ
.
∈
