Are Crossings Important for Drawing Large Graphs?

Kobourov, Stephen G. and Pupyrev, Sergey and Saket, Bahador (2014) Are Crossings Important for Drawing Large Graphs? In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 234-245 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_20).

Full text not available from this repository.

Abstract

Reducing the number of edge crossings is considered one of the most important graph drawing aesthetics. While real-world graphs tend to be large and dense, most of the earlier work on evaluating the impact of edge crossings utilizes relatively small graphs that are manually generated and manipulated. We study the effect on task performance of increased edge crossings in automatically generated layouts for graphs, from different datasets, with different sizes, and with different densities. The results indicate that increasing the number of crossings negatively impacts accuracy and performance time and that impact is significant for small graphs but not significant for large graphs. We also quantitatively evaluate the impact of edge crossings on crossing angles and stress in automatically constructed graph layouts. We find a moderate correlation between minimizing stress and the minimizing the number of crossings.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_20
Classifications:D Aesthetics > D.999 Others
G Algorithms and Complexity > G.420 Crossings
M Methods > M.400 Force-directed / Energy-based
P Styles > P.720 Straight-line
ID Code:1436

Repository Staff Only: item control page

References

Archambault, D., Purchase, C.H., Pinadu, B.: The readability of path-preserving clustering of graphs. EuroVis 29(3), 1173–1182 (2010)

Bateman, S., Mandryk, R.L., Gutwin, C., Genest, A., McDine, D., Brooks, C.: Useful junk? The effects of visual embellishment on comprehension and memorability of charts. In: CHI, pp. 2573–2582 (2010)

Buchheim, C., Chimani, M., Gutwenger, C., Jünger, M., Mutzel, P.: Crossings and planarization. In: Handbook of Graph Drawing and Visualization. CRC Press (2013)

Cabello, S., Mohar, B.: Adding one edge to planar graphs makes crossing number and 1-planarity hard. SIAM Journal on Computing 42(5), 1803–1829 (2013)

Dwyer, T., Lee, B., Fisher, D., Quinn, K.I., Isenberg, P., Robertson, G., North, C.: A comparison of user-generated and automatic graph layouts. IEEE Trans. Vis. Comput. Graphics 15(6), 961–968 (2009)

Ellson, J., Gansner, E.R., Koutsofios, L., North, S.C., Woodhull, G.: Graphviz - open source graph drawing tools. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 483–484. Springer, Heidelberg (2002)

Fruchterman, T.M., Reingold, E.M.: Graph drawing by force-directed placement. Software: Practice and Experience 21(11), 1129–1164 (1991)

Gansner, E.R., Koren, Y., North, S.C.: Graph drawing by stress majorization. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 239–250. Springer, Heidelberg (2005)

Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM Journal on Algebraic Discrete Methods 4(3), 312–316 (1983)

Harel, D., Koren, Y.: A fast multi-scale method for drawing large graphs. J. Graph Algorithms Appl. 6(3), 179–202 (2002)

Hliněnỳ, P.: Crossing number is hard for cubic graphs. J. Comb. Theory B 96(4), 455–471 (2006)

Hu, Y.: Efficient, high-quality force-directed graph drawing. Mathematica Journal 10(1), 37–71 (2005)

Huang, W., Huang, M.: Exploring the relative importance of number of edge crossings and size of crossing angles: A quantitative perspective. Advanced Intelligence 3(1), 25–42 (2014)

Huang, W., Eades, P., Hong, S.H.: Larger crossing angles make graphs easier to read. Visual Languages & Computing 1 (2014)

Huang, W., Hong, S.H., Eades, P.: Layout effects on sociogram perception. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 262–273. Springer, Heidelberg (2006)

Jianu, R., Rusu, A., Hu, Y., Taggart, D.: How to display group information on node–link diagrams: an evaluation. IEEE Trans. Vis. Comput. Graphics (to appear, 2014)

Kamada, T., Kawai, S.: An algorithm for drawing general undirected graphs. Inf. Proc. Let. 31(1), 7–15 (1989)

Koren, Y., Çivril, A.: The binary stress model for graph drawing. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 193–205. Springer, Heidelberg (2009)

Lee, B., Plaisant, C., Parr, C., Fekete, J.D., Henry, N.: Task taxonomy for graph visualization. In: BELIV, pp. 81–85. ACM Press (2006)

Purchase, H.C.: Which aesthetic has the greatest effect on human understanding? In: DiBattista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 248–261. Springer, Heidelberg (1997)

Purchase, H., Cohen, R., James, M.: Validating graph drawing aesthetics. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 435–446. Springer, Heidelberg (1996)

Saket, B., Simonetto, P., Kobourov, S., Börner, K.: Node, node-link, and node-link-group diagrams: An evaluation. In: IEEE InfoVis (to appear, 2014)

Ware, C., Purchase, H.C., Colpoys, L., McGill, M.: Cognitive measurements of graph aesthetics. Information Visualization 1(2), 103–110 (2002)