2014 | OriginalPaper | Buchkapitel
Trade-Offs in Planar Polyline Drawings
verfasst von : Stephane Durocher, Debajyoti Mondal
Erschienen in: Graph Drawing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 triangulations. 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 triangulation, our algorithm computes a drawing with angular resolution
r
/
d
(
v
) at each vertex
v
, and area
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.3 to 32.12
n
2
when
r
= 1.