An Experimental Evaluation of Multilevel Layout Methods

Bartel, Gereon and Gutwenger, Carsten and Klein, Karsten and Mutzel, Petra (2011) An Experimental Evaluation of Multilevel Layout Methods. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany , pp. 80-91 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_8).

Full text not available from this repository.

Abstract

Applying the multilevel paradigm to energy-based layout algorithms can improve both the quality of the resulting drawings as well as the running time of the layout computation. In order to do this, approaches for the different multilevel phases refinement, placement, layout, and optionally scaling and postprocessing need to be implemented. A number of multilevel layout algorithms have been proposed already, which differ in the way these phases are realized. We present an experimental study that investigates the influence of varying combinations with respect to running time and quality criteria.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_8
Classifications:M Methods > M.400 Force-directed / Energy-based
P Styles > P.720 Straight-line
ID Code:1196

Repository Staff Only: item control page

References

The Open Graph Drawing Framework, http://www.ogdf.net

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

Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice-Hall, Englewood Cliffs (1999)

Brandenburg, F.J., Himsolt, M., Rohrer, C.: An experimental comparison of force-directed and randomized graph drawing algorithms. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 76–87. Springer, Heidelberg (1996)

Brandes, U., Pich, C.: An experimental study on distance-based graph drawing. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 218–229. Springer, Heidelberg (2009)

Davidson, R., Harel, D.: Drawing graphs nicely using simulated annealing. ACM Trans. Graph. 15(4), 301–331 (1996)

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

Frishman, Y., Tal, A.: Multi-level graph layout on the GPU. IEEE Transactions on Visualization and Computer Graphics 13(6), 1310–1319 (2007)

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

Gajer, P., Kobourov, S.G.: GRIP: Graph drawing with intelligent placement. J. Graph Algorithms Appl. 6(3), 203–224 (2002)

Godiyal, A., Hoberock, J., Garland, M., Hart, J.C.: Rapid multipole graph drawing on the GPU. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 90–101. Springer, Heidelberg (2009)

Gronemann, M.: Engineering the fast-multipole-multilevel method for multicore and SIMD architectures. Master’s thesis, Technische Universität Dortmund (2009)

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)

Hachul, S., Jünger, M.: Large-graph layout algorithms at work: An experimental study. J. Graph Algorithms Appl. 11(2), 345–369 (2007)

Han, K., Ju, B.-H., Park, J.H.: InterViewer: Dynamic visualization of protein-protein interactions, http://interviewer.inha.ac.kr/

Kamada, T., Kawai, S.: An algorithm for drawing general undirected graphs. Information Processing Letters 31(1), 7–15 (1989)

Kaufmann, M., Wagner, D. (eds.): Drawing Graphs. LNCS, vol. 2025. Springer, Heidelberg (2001)

Walshaw, C.: The graph partitioning archive, http://staffweb.cms.gre.ac.uk/~c.walshaw/partition/

Walshaw, C.: A multilevel algorithm for force-directed graph-drawing. J. Graph Algorithms Appl. 7(3), 253–285 (2003)