Information Technology Reference
In-Depth Information
- If the number of points of
B
that lie on
l
v
k
is
z
,where
z
h
,thenweroute
the extensions of
l
v
k
through
z
consecutive grid points lying on the left
side of
A
v
k
immediately below
L
(
v
k
). We then route the extensions on
l
v
k
through the next consecutive grid points along the same vertical line. Since
there are at most
d
m
(
v
k
)
m
-edges, we need at most
d
(
v
) consecutive grid
points below
L
(
v
k
). Figure 6(d) illustrates such a scenario, where
h
=2.
- If the number of points of
B
that lie on
l
v
k
is at most
z
,where
z
≤
≤
h
,
then the drawing is symmetric to the case when
z<h
.
-Otherwise,both
l
v
k
and
l
v
k
contains more than
h
extensions. In this case
min
z,z
}
z,z
}≤
h
.Wefirstextendthe
extensions on
l
v
k
to the grid points that lie consecutively to the left of
A
v
(on the first line of
S
v
k
). We then extend the extensions on
l
v
k
to the
grid points that lie consecutively below of
A
v
(on the last line of
S
v
k
).
Finally, we connect all these new extensions directly to
C
(
v
k
). Note that
the maximum horizontal (respectively, vertical) distance between
C
(
v
)and
a bend point on
l
v
k
(respectively,
l
v
k
)isatmost(
d
m
(
v
)
{
>h
, and hence max
{
d
m
(
v
)
−
d
(
v
).
Routing
l
-edges:
Let
u
1
,u
2
,...,u
q
be the vertices in top-to-bottom order
that are incident to
D
(
v
k
) by incoming
l
-edges. Let
be the nearest vertical
grid line to the right of
S
v
, and remove the parts of these
l
-edges that lie
in between
D
(
v
k
)and
(except for the
l
-edge incident to
C
(
v
k
)). We then
connect these extensions to the
q
consecutive grid points on the first line
of
S
v
k
that lie immediately below the top-right corner of
A
v
. Finally, we
connect all these new extensions directly to
C
(
v
k
).
Routing
r
-edges:
This scenario is symmetric for routing
l
-edges.
−
h
)+
h
≤
Angular Resolution and Area:
In all the cases, the smallest angle
ʸ
at any
vertex
v
is equal to the angle determined by the points (
−d
(
v
)
,−h
)and(
−d
(
v
)+
1
,
h
)at
C
(
v
)=(0
,
0), as illustrated in Figure 6(e). Here the angular resolution
is at least
−
ʲ
v
1, and the area is (6
ʲ
+2
/
3)
2
n
2
.We
d
(
v
)(1+
ʲ
v
)
,where1
/d
(
v
)
≤
ʲ
v
≤
omit the details due to space constraints.
Theorem 3.
Every n-vertex maximal planar graph admits a
2
-bend polyline
drawing with angular resolution
ʲ
d
(
v
)(1+
ʲ
2
)
for each vertex v,andarea
(6
nʲ
+
W
+2)
×
(6
nʲ
+
H
+2)
.Hereʲ
∈
[1
/
3
,
1]
,andW
+
H
≤
(4
n
−
2
Δ
0
−
10)
/
3
.
5Con lu on
In this paper we have given the first smooth trade-off between the area and
angular resolution for 2-bend polyline drawings of any given planar graph. Our
algorithm dominates all the previous 2-bend polyline drawing algorithms except
Duncan and Kobourov's algorithm [10], which uses 1-bend per edge and dom-
inates our algorithm when the angular resolution is in the interval [0
.
38
/d
(
v
)
,
0
.
5
/d
(
v
)]. Similar to the previously known polyline drawing algorithms, one can
implement our algorithm using standard techniques [6] such that the drawings
are computed in linear time.
