Topology-Driven Force-Directed Algorithms

Didimo, Walter and Liotta, Giuseppe and Romeo, Salvatore (2011) Topology-Driven Force-Directed Algorithms. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany, , pp. 165-176 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_15).

Full text not available from this repository.

Abstract

This paper studies the problem of designing graph drawing algorithms that guarantee good trade-offs in terms of number of edge crossings, crossing angle resolution, and geodesic edge tendency. It describes two heuristics designed within the topology-driven force-directed framework that combines two classical graph drawing approaches: the force-directed approach and a planarization-based approach (e.g., the topology-shape-metrics approach). An extensive experimental analysis on two different test suites of graphs shows the effectiveness of the proposed solutions for the optimization of some readability metrics.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_15
Classifications:M Methods > M.400 Force-directed / Energy-based
ID Code:1203

Repository Staff Only: item control page

References

Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., Vargiu, F.: An experimental comparison of four graph drawing algorithms. Comput. Geom. 7, 303–325 (1997)

Bertault, F.: A force-directed algorithm that preserves edge crossing properties. In: Kratochvíl, J. (ed.) GD 1999. LNCS, vol. 1731, pp. 351–358. Springer, Heidelberg (1999)

Bertolazzi, P., Di Battista, G., Didimo, W.: Computing orthogonal drawings with the minimum number of bends. IEEE Trans. on Computers 49(8), 826–840 (2000)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice-Hall, Upper Saddle River (1999)

Didimo, W., Liotta, G., Romeo, S.A.: Graph visualization techniques for conceptual web site traffic analysis. In: PacificVis, pp. 193–200. IEEE, Los Alamitos (2010)

Didimo, W., Pizzonia, M.: Upward embeddings and orientations of undirected planar graphs. J. Graph Algorithms Appl. 7(2), 221–241 (2003)

Dunne, C., Shneiderman, B.: Improving graph drawing readability by incorporating readability metrics: A software tool for network analysts. Technical report (2009)

Dwyer, T.: Scalable, versatile and simple constrained graph layout. Comput. Graph. Forum 28(3), 991–998 (2009)

Dwyer, T., Marriott, K., Schreiber, F., Stuckey, P.J., Woodward, M., Wybrow, M.: Exploration of networks using overview+detail with constraint-based cooperative layout. IEEE Trans. Vis. Comput. Graph. 14(6), 1293–1300 (2008)

Dwyer, T., Marriott, K., Wybrow, M.: Topology preserving constrained graph layout. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 230–241. Springer, Heidelberg (2009)

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

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)

Fößmeier, U., Kaufmann, M.: Drawing high degree graphs with low bend numbers. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 254–266. Springer, Heidelberg (1996)

Garg, A., Tamassia, R.: A new minimum cost flow algorithm with applications to graph drawing. In: North, S.C. (ed.) GD 1996. LNCS, vol. 1190, pp. 201–216. Springer, Heidelberg (1997)

Gutwenger, C., Mutzel, P., Weiskircher, R.: Inserting an edge into a planar graph. Algorithmica 41(4), 289–308 (2005)

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)

Huang, W.: Using eye tracking to investigate graph layout effects. In: APVIS, pp. 97–100 (2007)

Huang, W., Hong, S.-H., Eades, P.: Effects of crossing angles. In: PacificVis, pp. 41–46. IEEE, Los Alamitos (2008)

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

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.C., Carrington, D.A., Allder, J.-A.: Empirical evaluation of aesthetics-based graph layout. Empirical Software Engineering 7(3), 233–255 (2002)

Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM Journal on Computing 16(3), 421–444 (1987)

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