Force-Directed Lombardi-Style Graph Drawing

Chernobelskiy, Roman and Cunningham, Kathryn I. and Goodrich, Michael T. and Kobourov, Stephen G. and Trott, Lowell (2012) Force-Directed Lombardi-Style Graph Drawing. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 320-331 (Official URL: http://dx.doi.org/ 10.1007/978-3-642-25878-7_31).

Full text not available from this repository.

Abstract

A Lombardi drawing of a graph is one in which vertices are represented as points, edges are represented as circular arcs between their endpoints, and every vertex has perfect angular resolution (equal angles between consecutive edges, as measured by the tangents to the circular arcs at the vertex). We describe two algorithms that create “Lombardi-style” drawings (which we also call near-Lombardi drawings), in which all edges are still circular arcs, but some vertices may not have perfect angular resolution. Both of these algorithms take a force-directed, spring-embedding approach, with one using forces at edge tangents to produce curved edges and the other using dummy vertices on edges for this purpose. As we show, these approaches produce near-Lombardi drawings, with one being slightly better at achieving near-perfect angular resolution and the other being slightly better at balancing edge placements.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_31
Classifications:M Methods > M.400 Force-directed / Energy-based
P Styles > P.300 Curved
ID Code:1266

Repository Staff Only: item control page

References

Brandenburg, F., Himsolt, M., Rohrer, C.: An Experimental Comparison of Force-Directed And Randomized Graph Drawing Algorithms. In: North, S.C. (ed.) GD 1996. LNCS, vol. 1190, pp. 76–87. Springer, Heidelberg (1997)

Brandes, U.: Drawing on Physical Analogies. In: Kaufmann, M., Wagner, D. (eds.) Drawing Graphs. LNCS, vol. 2025, pp. 71–86. Springer, Heidelberg (2001)

Brandes, U., Schlieper, B.: Angle and Distance Constraints On Tree Drawings. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 54–65. Springer, Heidelberg (2007)

Brandes, U., Shubina, G., Tamassia, R.: Improving angular resolution in visualizations of geographic networks. In: 2nd TCVG Symp. Visualization, pp. 23–32 (2000)

Brandes, U., Wagner, D.: Using Graph Layout to Visualize Train Interconnection Data. J. Graph Algorithms Appl. 4(3), 135–155 (2000)

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

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall PTR, Upper Saddle River (1998)

Di Battista, G., Vismara, L.: Angles of planar triangular graphs. SIAM J. Discrete Math. 9(3), 349–359 (1996)

Dickerson, M., Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent drawings: Visualizing non-planar diagrams in a planar way. J. Graph Algorithms Appl. 9(1), 31–52 (2005)

Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Löffler, M.: Planar and Poly-Arc Lombardi Drawings. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 308–319. Springer, Heidelberg (2011)

Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Nöllenburg, M.: Drawing Trees with Perfect Angular Resolution and Polynomial Area. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 183–194. Springer, Heidelberg (2011)

Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Nöllenburg, M.: Lombardi Drawings of Graphs. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 195–207. Springer, Heidelberg (2011)

Eades, P.: A heuristic for graph drawing. Congressus Numerantium 42, 149–160 (1984)

Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent layered drawings. Algorithmica 47(4), 439–452 (2007)

Finkel, B., Tamassia, R.: Curvilinear Graph Drawing Using the Force-Directed Method. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 448–453. Springer, Heidelberg (2005)

Fruchterman, T., Reingold, E.: Graph drawing by force-directed placement. Softw. – Pract. Exp. 21(11), 1129–1164 (1991)

Gajer, P., Goodrich, M.T., Kobourov, S.G.: A multi-dimensional approach to force-directed layouts of large graphs. Comp. Geometry: Theory and Applications 29(1), 3–18 (2004)

Gajer, P., Kobourov, S.G.: GRIP: Graph dRawing with Intelligent Placement. Journal of Graph Algorithms and Applications 6(3), 203–224 (2002)

Garg, A., Tamassia, R.: Planar drawings and angular resolution: algorithms and bounds. In: 2nd European Symposium on Algorithms, London, UK, pp. 12–23 (1994)

Goodrich, M.T., Wagner, C.G.: A framework for drawing planar graphs with curves andpolylines. J. 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)

Hirsch, M., Meijer, H., Rappaport, D.: Biclique Edge Cover Graphs and Confluent Drawings. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 405–416. Springer, Heidelberg (2007)

Holten, D., van Wijk, J.J.: Force-directed edge bundling for graph visualization. Computer Graphics Forum 28, 983–990 (2009)

Lombardi, M., Hobbs, R.: Mark Lombardi: Global Networks. Independent Curators (2003)

Malitz, S., Papakostas, A.: On the angular resolution of planar graphs. SIAM J. Discrete Math. 7(2), 172–183 (1994)

Matsakis, N.: Transforming a random graph drawing into a Lombardi drawing. arXiv ePrints, abs/1012.2202 (2010)

Purchase, H.: Which Aesthetic Has The Greatest Effect On Human Understanding? In: Di Battista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 248–261. Springer, Heidelberg (1997)

Purchase, H.C., Cohen, R.F., James, M.: Validating Graph Drawing Aesthetics. In: North, S.C. (ed.) GD 1996. LNCS, vol. 1190, pp. 435–446. Springer, Heidelberg (1997)