Information Technology Reference
In-Depth Information
Property A:
no VV overlap
Property B:
no VP overlap
Property C:
no PP overlap
Fig. 1.
Venn diagram describing the logical relationships amongProperties A-C
x
(
r
) and
y
(
r
) are the
x
-and
y
-coordinate of a point
r
, respectively. The
Euclidean
distance
d
2
(
p,q
) of
p
and
q
is defined as
d
2
(
p,q
)=(
dx
(
p,q
)
2
+
dy
(
p,q
)
2
)
2
.The
Manhattan distance
is defined as
d
1
(
p,q
)=
dx
(
p,q
)+
dy
(
p,q
).The
uniform distance
d
∞
(
p,q
) = lim
iₒ∞
(
dx
(
p,q
)
i
+
dy
(
p,q
)
i
)
i
=max(
dx
(
p,q
)
,dy
(
p,q
)).
We define the A
NCHORED
G
RAPH
D
RAWING
problem parametrically in the metric
L
k
and the drawing style
X
, which can be straight-line (
X
=
S
) or rectilinear (
X
=
R
). Hence, for any
L
k
∈{
L
1
,L
2
,L
∞
}
and any
X∈{S
,
R}
we define:
Problem:
A
NCHORED
G
RAPH
D
RAWING
-
L
k
-
X
(AGD-
L
k
-
X
).
Instance:
A graph
G
=(
V,E
),
2
, and a distance
ʴ
.
Question:
Does
an initial placement for its vertices
ʱ
(
v
):
V
ₒ
there exist a planar drawing of
G
according to the
X
drawing convention such that each
vertex
v
V
is at distance
L
k
at most
ʴ
from
ʱ
(
v
)?
We d e fi n e
anchored drawing
aplanardrawing satisfying all the requirements of the
particular version of problem A
NCHORED
G
RAPH
D
RAWING
.
Given an instance
∈
of the A
NCHORED
G
RAPH
D
RAWING
problem, each
vertex
v
identifies a region
R
(
v
) of the plane, called
vertex region
, that encloses the
initial position of the vertex and whose shape depends on the metric adopted for com-
puting the distance. In particular, for the Euclidean distance the vertex regions are cir-
cles, for the Manhattan distance they are diamonds, and for the uniform distance they
are squares. Each edge (
u,v
) of the graph, instead, identifies a
pipe
P
(
u,v
),defined
as follows. Consider the convex hull
H
of
R
(
u
) and
R
(
v
);pipe
P
(
u,v
) is the closed
region obtained by removing
R
(
u
) and
R
(
v
) from
H
.
Instances can be classified based on the intersections among vertex and pipe regions.
Namely, we can have instances satisfying the following properties:
Property A.
No overlap between two vertex regions (VV-overlaps);
Property B.
No overlap between a vertex region and a pipe (VP-overlaps);
Property C.
No overlap between pipes (PP-overlaps) not incident to the same vertex.
The Venn diagram in Fig.1showsthelogical relationships between the three prop-
erties. The following observation is immediate.
G, ʱ, ʴ
Observation 1.
If Properties A, B, andCare all satisfied, then theinstance is trivially
positive, since choosing any pointin the vertex region (including theinitialplacement
of the vertex) yields an anchored drawing of theinput graph.
