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, Würzburg, Germany , 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
ID Code:1442

Repository Staff Only: item control page

References

Biedl, T.C., Kaufmann, M.: Area-efficient static and incremental graph drawings. In: Burkard, R.E., Woeginger, G.J. (eds.) ESA 1997. LNCS, vol. 1284, pp. 37–52. Springer, Heidelberg (1997)

Bonichon, N., Felsner, S., Mosbah, M.: Convex drawings of 3-connected plane graphs. Algorithmica 47(4), 399–420 (2007)

Bonichon, N., Le Saëc, B., Mosbah, M.: Wagner’s theorem on realizers. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 1043–1053. Springer, Heidelberg (2002)

Brandenburg, F.J.: Drawing planar graphs on 89n2 area. Electronic Notes in Discrete Mathematics 31, 37–40 (2008)

Cheng, C.C., Duncan, C.A., Goodrich, M.T., Kobourov, S.G.: Drawing planar graphs with circular arcs. Discrete & Computational Geometry 25(3), 405–418 (2001)

Chrobak, M., Payne, T.: A linear-time algorithm for drawing planar graphs. Information Processing Letters 54, 241–246 (1995)

CircuitLogix, https://www.circuitlogix.com/ (accessed June 03, 2014)

ConceptDraw: http://www.conceptdraw.com/ (accessed June 03, 2014)

De Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)

Duncan, C.A., Kobourov, S.G.: Polar coordinate drawing of planar graphs with good angular resolution. Journal of Graph Algorithms and Applications 7(4), 311–333 (2003)

Durocher, S., Mondal, D.: On balanced +-contact representations. In: Proceedings of GD. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 143–154. Springer, Heidelberg (2013)

Goodrich, M.T., Wagner, C.G.: A framework for drawing planar graphs with curves and polylines. Journal of Algorithms 37(2), 399–421 (2000)

Gutwenger, C., Mutzel, P.: Planar polyline drawings with good angular resolution. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 167–182. Springer, Heidelberg (1999)

Hong, S.H., Mader, M.: Generalizing the shift method for rectangular shaped vertices with visibility constraints. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 278–283. Springer, Heidelberg (2009)

Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4–32 (1996)

Kurowski, M.: Planar straight-line drawing in an o(n)×o(n) grid with angular resolution ω(1/n). In: Vojtáš, P., Bieliková, M., Charron-Bost, B., Sýkora, O. (eds.) SOFSEM 2005. LNCS, vol. 3381, pp. 250–258. Springer, Heidelberg (2005)

Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of ACM-SIAM SODA, January 22-24, pp. 138–148. ACM (1990)

SmartDraw Software, LLC, http://www.smartdraw.com/ (accessed June 03, 2014)

Tamassia, R., Di Battista, G., Batini, C.: Automatic graph drawing and readability of diagrams. IEEE Transactions on Systems, Man and Cybernetics 18(1), 61–79 (1988)

Zhang, H.: Planar polyline drawings via graph transformations. Algorithmica 57(2), 381–397 (2010)

Zhang, H., He, X.: Canonical ordering trees and their applications in graph drawing. Discrete & Computational Geometry 33(2), 321–344 (2005)