Improving Layered Graph Layouts with Edge Bundling

Pupyrev, Sergey and Nachmanson, Lev and Kaufmann, Michael (2011) Improving Layered Graph Layouts with Edge Bundling. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany , pp. 329-340 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_30).

Full text not available from this repository.

Abstract

We show how to improve the Sugiyama scheme by edge bundling. Our method modifies the layout produced by the Sugiyama scheme by bundling some of the edges together. The bundles are created by a new algorithm based on minimizing the total ink needed to draw the graph edges. We give several implementations that vary in quality of the resulting layout and execution time. To diminish the number of edge crossings inside of the bundles we apply a metro-line crossing minimization technique. The method preserves the Sugiyama style of the layout and creates a more readable view of the graph.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_30
Classifications:P Styles > P.480 Layered
ID Code:1218

Repository Staff Only: item control page

References

Argyriou, E., Bekos, M.A., Kaufmann, M., Symvonis, A.: Two polynomial time algorithms for the metro-line crossing minimization problem. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 336–347. Springer, Heidelberg (2009)

Bekos, M.A., Kaufmann, M., Potika, K., Symvonis, A.: Line crossing minimization on metro maps. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 231–242. Springer, Heidelberg (2008)

Cui, W., Zhou, H., Qu, H., Wong, P.C., Li, X.: Geometry-based edge clustering for graph visualization. IEEE Transactions on Visualization and Computer Graphics 14, 1277–1284 (2008)

Eades, P., Sugiyama, K.: How to draw a directed graph. Journal of Information Processing 14(4), 424–437 (1990)

Eiglsperger, M., Siebenhaller, M., Kaufmann, M.: An efficient implementation of sugiyamas algorithm for layered graph drawing. Journal of Graph Algorithms and Applications 9(3), 305–325 (2005)

Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent layered drawings. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 184–194. Springer, Heidelberg (2005)

Gansner, E.R., Koren, Y.: Improved circular layouts. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 386–398. Springer, Heidelberg (2007)

Gansner, E.R., Koutsofios, E., North, S.C., Vo, K.-P.: A technique for drawing directed graphs. IEEE Transactions on Software Engineering 19(3), 214–230 (1993)

Holten, D.: Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data. IEEE Transactions on Visualization and Computer Graphics 12(5), 741–748 (2006)

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

Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Physical Review E 80(1) (2008)

Nachmanson, L., Robertson, G., Lee, B.: Drawing graphs with GLEE. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 389–394. Springer, Heidelberg (2008)

Newbery, F.J.: Edge concentration: A method for clustering directed graphs. In: Proc. 2nd Int. Workshop on Software Configuration Management, pp. 76–85 (1989)

Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. on Systems, Man, and Cybernetics 11(2), 109–125 (1981)

Tufte, E.R.: The Visual Display of Quantitative Information. Graphics Press, CT (1983)

The AT&T graph collection. http://www.graphdrawing.org.

http://research.microsoft.com/en-us/projects/specexplorer.