Information Technology Reference
In-Depth Information
200
35
30
Area
in
n
2
25
20
15
10
5
0.2
0.3 0.4
0.6 0.
7 0.8 0.9 1
Angular Resolution in 1
/d
(
v
)
0.5
Fig. 2.
Trade-off between angular resolution and area for 2-bend polyline drawings,
where the bold line denotes the trade-off established in this paper. The square, circle
and diamond denote the reference [10], [12] and [5], respectively.
Early polyline drawing algorithms were developed as a generalization of or-
thogonal drawings [1]. Before Duncan and Kobourov's algorithm [10], all the
polyline drawing techniques with good angular resolution and
O
(
n
2
)areawere
based on the idea of assigning an empty square surrounding each vertex (e.g.,
Figure 1(c)), which forced the constant factor in the
O
(
.
) notation to be very
large. The algorithm of Duncan and Kobourov [10] finds a drawing with smaller
area, but loses the square-emptiness property around the vertices, as well as
decreasing the angular resolution by a factor of 2. Observe that two solutions
in a multi-objective optimization are comparable if and only if one of them
dominates the other with respect to every optimization criteria. Hence although
the drawing of [10] has smaller area than that of [5] (see Table 1), it is not an
improvement over [5] because of its lower angular resolution.
Contributions.
In this paper we examine the trade-offs between the angular
resolution and area for 2-bend polyline drawings of planar triangulations. Fig-
ure 2 illustrates the solution space dominated by our algorithm in gray, which
dominates all the previous 2-bend polyline drawing algorithms except Duncan
and Kobourov's algorithm [10], which dominates our algorithm along a small
interval of
X
-axis. Even under the model where each vertex
v
is surrounded by
an empty square of size
d
(
v
)
d
(
v
), we can construct a 2-bend polyline drawing
with angular resolution 1
/Δ
and area 32
.
12
n
2
, where the best known bounds can
achieve an
ʩ
(1
/d
(
v
)) angular resolution with an area at least 200
n
2
[5,12,14],
or an 1
/Δ
angular resolution with 3 bends per edge [13].
×
2 Technical Background
Let
G
be a
plane graph
, i.e., a planar graph with a fixed combinatorial em-
bedding and a specified outerface. If every face of
G
including (respectively,
excluding) the outer face is a cycle of length three, then
G
is called
triangulated
(respectively,
internally triangulated
). Let
G
be an
n
-vertex triangulated plane
graph, where
v
1
,v
2
and
v
n
are the outer vertices of
G
in clockwise order, and
