Information Technology Reference
In-Depth Information
Trade-Offs in Planar Polyline Drawings
Stephane Durocher
∗
and Debajyoti Mondal
∗∗
Department of Computer Science, University of Manitoba, Canada
{
durocher,jyoti
}
@cs.umanitoba.ca
Abstract.
Angular resolution, area and the number of bends are some
important aesthetic criteria of a polyline drawing. Although trade-offs
among these criteria have been examined over the past decades, many
of these trade-offs are still not known to be optimal. In this paper we
give a new technique to compute polyline drawings for planar trian-
gulations. Our algorithm is simple and intuitive, yet implies significant
improvement over the known results. We present the first smooth trade-
off between the area and angular resolution for 2-bend polyline drawings
of any given planar graph. Specifically, for any given
n
-vertex triangula-
tion, our algorithm computes a drawing with angular resolution
r/d
(
v
)
at each vertex
v
,andarea
f
(
n, r
), for any
r ∈
(0
,
1], where
d
(
v
) denotes
the degree at
v
.For
r<
0
.
389 or
r>
0
.
5,
f
(
n, r
) is less than the drawing
area required by previous algorithms;
f
(
n, r
) ranges from 7
.
12
n
2
when
r ≤
0
.
3to32
.
12
n
2
when
r
=1.
1 Introduction
Polyline drawing is a classic style of drawing planar graphs, which has a wide
range of applications in the area of software visualization [8,18] and layout of
circuit diagrams [7]. Given an
n
-vertex planar graph
G
,a
polyline drawing ʓ
of
G
maps each vertex to a distinct point in
2
, and each edge to a simple polygonal
chain between its endpoints such that no two edges intersect except possibly at
their common end point.
ʓ
is a
k-bend polyline drawing
if the number of line
segments per edge is bounded by at most
k
+ 1, i.e., each edge contains at most
k
bend points. Consequently, a
k
-bend polyline drawing can be considered as
a(
k
+
ʻ
)-bend drawing for any
ʻ>
0. Figures 1(a) and (b) illustrate a plane
graph
G
and a 2-bend polyline drawing of
G
, respectively.
Researchers have examined the theoretical aspects of planar polyline drawings
over a long time [2,4,9,10,13,17,20].
Area
(i.e., the size of the smallest integer grid
containing the drawing),
angular resolution
(i.e., the smallest angle formed at
any vertex), number of bends per edge, edge separation and bend resolution are
some examples of such aesthetic criteria. Even after decades of research effort,
finding the optimal trade-off between the number of total bends and area still
R
∗
Work of the author is supported in part by the Natural Sciences and Engineering
Research Council of Canada (NSERC).
∗∗
Work of the author is supported in part by a University of Manitoba Graduate
Fellowship.
