Information Technology Reference
In-Depth Information
In this paper we always assume that Property A is satisfied. In fact, if vertex regions
were allowed to overlap, then it would be possible to reduce to this problem a variant
of the Clustered Planarity problem whose complexity is still unknown. In this variant,
which includes Strip Planarity [2] as a special case, the cluster regions are already drawn
and edges are straight-line.
Two further observations can be made which reduce the set of instances of interest.
Observation 2.
An instance satisfying Property Bbut not satisfying Property C(i.e.,
withPP-overlaps but withoutVP-overlaps) is trivially false, asin this case any PP-
overlap would enforce a crossing between twoedges for any placementoftheir end-
vertices in thecorresponding vertex regions.
Observation 3.
An instance satisfying Property Cbut not satisfying Property B(i.e.,
with VP-overlaps but without PP-overlaps) is trivially true.
Proof:
Since Property C holds, no crossing can occuroutside a vertex region. First,
suppose that regions are diamonds or squares. If the center of region
R
(
v
) of a vertex
v
lies inside a pipe
P
(
x, y
), then at least two consecutive vertices, say
a
and
b
, delimiting
R
(
v
) lie inside
P
(
x, y
).Thisimpliesthat
v
has degree at most 1, as otherwise there
would be a
PP
-overlap between
P
(
x, y
) and a pipe
P
(
v,w
) delimited by either
a
or
b
.
As for the case in which regions are circles, if the center of
R
(
v
) lies inside
P
(
x, y
),
then at least half of the circle delimiting
R
(
v
) lies inside
P
(
x, y
). Hence, a similar
argument applies to prove that deg(
v
)
≤
1.
In all the three cases, since deg(
v
)
≤
1 and
R
(
v
) is not completely contained into
P
(
x, y
),
v
can be placed on any point of
R
(
v
) outside
P
(
x, y
). Hence, placing each
other vertex at the center of its region yields an anchored drawing.
Due to the above properties and observations, the remaining part of this paper focuses
on the instances for which Property A holds, while Properties B and C do not. These
instances correspond to the blueregion at the top of Fig.1.
3
Polynomial-Time Algorithm
In this section we describe an algorithm, called
Algo-AGD-
L
∞
-
R
, that decides in poly-
nomial time instances
G, ʱ, ʴ
of problem AGD-
L
∞
-
R
such that
G
is connected.
V
, denote by
x
l
(
v
) and
x
r
(
v
) the
x
-coordinate of the left and
right side of
R
(
v
), respectively. Similarly, denote by
y
t
(
v
) and
y
b
(
v
) the
y
-coordinate
of the top and bottom side of
R
(
v
), respectively. See region
R
(
u
) in Fig.2.
First note that, for each edge (
u,v
)
For each vertex
v
∈
E
, the relative placement of
R
(
u
) and
R
(
v
)
determines whether (
u,v
) has to be drawn as a vertical or a horizontal segment, or
(
u,v
) cannot be drawn neither horizontal nor vertical with its endpoints lying inside
their corresponding regions. In the latter case, instance
I
is negative. An edgethathas
to be drawn as a horizontal (vertical) segment is a
horizontal
(
vertical
)edge. In the fol-
lowing we assume w.l.o.g. that any horizontal edge (
u,v
) is such that
x
r
(
u
)
<x
l
(
v
),
while any vertical edge (
u,v
) is such that
y
t
(
u
)
<y
b
(
v
). A path composed only of
horizontal (vertical) edges is a
horizontal
(
vertical
) path. Given that each edge (
u,v
)
∈
