Exploring Complex Drawings via Edge Stratification

Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Montecchiani, Fabrizio and Tollis, Ioannis G. (2013) Exploring Complex Drawings via Edge Stratification. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 304-315 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_27).

Full text not available from this repository.


We propose an approach that allows a user to explore a layout produced by any graph drawing algorithm, in order to reduce the visual complexity and clarify its presentation. Our approach is based on stratifying the drawing into layers with desired properties; layers can be explored and combined by the user to gradually acquire details. We present stratification heuristics, a user study, and an experimental analysis that evaluates how our stratification heuristics behave on the drawings computed by a variety of popular force-directed algorithms.

Item Type:Conference Paper
Classifications:M Methods > M.400 Force-directed / Energy-based
P Styles > P.720 Straight-line
ID Code:1384

Repository Staff Only: item control page


Auber, D., Chiricota, Y., Jourdan, F., Melançon, G.: Multiscale visualization of small world networks. In: InfoVis 2003, pp. 75–81. IEEE (2003)

Barabasi, A.-L., Albert, R.: Emergence of Scaling in Random Networks. Science 286(5439), 509–512 (1999)

Batagelj, V., Brandenburg, F., Didimo, W., Liotta, G., Palladino, P., Patrignani, M.: Visual analysis of large graphs using (X,Y)-clustering and hybrid visualizations. IEEE TVCG 17(11), 1587–1598 (2011)

Brandes, U., Pich, C.: More flexible radial layout. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 107–118. Springer, Heidelberg (2010)

Brélaz, D.: New methods to color the vertices of a graph. Comm. ACM 22, 251–256 (1979)

Bruckdorfer, T., Cornelsen, S., Gutwenger, C., Kaufmann, M., Montecchiani, F., Nöllenburg, M., Wolff, A.: Progress on partial edge drawings. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 67–78. Springer, Heidelberg (2013)

Brunel, E., Gemsa, A., Krug, M., Rutter, I., Wagner, D.: Generalizing geometric graphs. In: Speckmann, B. (ed.) GD 2011. LNCS, vol. 7034, pp. 179–190. Springer, Heidelberg (2011)

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

Chrobak, M., Nishizeki, T.: Improved edge-coloring algorithms for planar graphs. J. Algo. 11(1), 102–116 (1990)

Di Giacomo, E., Didimo, W., Liotta, G., Montecchiani, F.: h-quasi planar drawings of bounded treewidth graphs in linear area. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) WG 2012. LNCS, vol. 7551, pp. 91–102. Springer, Heidelberg (2012)

Di Giacomo, E., Didimo, W., Liotta, G., Montecchiani, F.: Area requirement of graph drawings with few crossings per edge. Comp. Geom. 46(8), 909–916 (2013)

Didimo, W., Liotta, G.: The crossing angle resolution in graph drawing. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory. Springer (2012)

Didimo, W., Montecchiani, F.: Fast layout computation of hierarchically clustered networks: Algorithmic advances and experimental analysis. In: IV 2012, pp. 18–23 (2012)

Dillencourt, M.B., Eppstein, D., Hirschberg, D.S.: Geometric thickness of complete graphs. Jour. Graph. Alg. and Appl. 4(3), 5–17 (2000)

Duncan, C.A., Eppstein, D., Kobourov, S.G.: The geometric thickness of low degree graphs. In: SoCG 2004, pp. 340–346. ACM (2004)

Frick, A., Ludwig, A., Mehldau, H.: A fast adaptive layout algorithm for undirected graphs. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 388–403. Springer, Heidelberg (1995)

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

Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. PNAS 99(12), 7821–7826 (2002)

Hachul, S., Jünger, M.: Drawing large graphs with a potential-field-based multilevel algorithm. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 285–295. Springer, Heidelberg (2005)

Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718–720 (1981)

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

Knuth, D.E.: The Stanford Graphbase: A Platform for Combinatorial Computing. Addison-Wesley Professional (1993)

Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78(4) (2008)

Michael Fire, Y.E., Puzis, R.: Organization mining using online social networks (2012), http://proj.ise.bgu.ac.il/sns

Mutzel, P., Jünger, M., Leipert, S. (eds.): GD 2001. LNCS, vol. 2265. Springer, Heidelberg (2002)

Purchase, H.C.: Effective information visualisation: a study of graph drawing aesthetics and algorithms. Interact. Comput. 13(2), 147–162 (2000)

Purchase, H.C., Carrington, D.A., Allder, J.-A.: Empirical evaluation of aesthetics-based graph layout. Empir. Softw. Eng. 7(3), 233–255 (2002)

Purchase, H.C., Hamer, J., Nöllenburg, M., Kobourov, S.G.: On the usability of lombardi graph drawings. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 451–462. Springer, Heidelberg (2013)

Shneiderman, B., Dunne, C.: Interactive network exploration to derive insights: Filtering, clustering, grouping, and simplification. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 2–18. Springer, Heidelberg (2013)

van Ham, F., van Wijk, J.J.: Interactive visualization of small world graphs. In: InfoVis 2004, pp. 199–206. IEEE (2004)

Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Diskret. Analiz No. 3, 25–30 (1964)

Zhou, H., Xu, P., Yuan, X., Qu, H.: Edge bundling in information visualization. Tsinghua Science and Technology 18(2), 145–156 (2013)