Trade-Offs in Planar Polyline Drawings

Durocher, Stephane and Mondal, Debajyoti (2014) Trade-Offs in Planar Polyline Drawings. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 306-318(Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_26).

Full text not available from this repository.

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 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.12n 2 when r ≤ 0.3 to 32.12n 2 when r = 1.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_26
Classifications: D Aesthetics > D.001 General
G Algorithms and Complexity > G.210 Bends
G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.999 Others
P Styles > P.540 Planar
P Styles > P.600 Poly-line
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 22 May 2015 09:04
Last Modified: 22 May 2015 09:04
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1442

Actions (login required)

View Item View Item