Shape-Based Quality Metrics for Large Graph Visualization

Eades, Peter and Hong, Seok-Hee and Klein, Karsten and Nguyen, An (2015) Shape-Based Quality Metrics for Large Graph Visualization. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 502-514 (Official URL:

Full text not available from this repository.


We propose a new family of quality metrics for graph drawing; in particular, we concentrate on larger graphs. We illustrate these metrics with examples and apply the metrics to data from previous experiments, leading to the suggestion that the new metrics are effective.

Item Type:Conference Paper
Classifications:D Aesthetics > D.999 Others
ID Code:1515

Repository Staff Only: item control page


Chimani, M., et al.: Graph drawings with less stress and fewer crossings are preferable. In: Duncan, C., Symvonis, A. (eds.) GD2014. LNCS, vol. 8871, pp. 523–524. Springer, Heidelberg (2014)

Eades, P., Whitesides, S.: The realization problem for euclidean minimum spanning trees in NP-hard. Algorithmica 16(1), 60–82 (1996)

Edelsbrunner, H., Kirkpatrick, D.G., Seidel, R.: On the shape of a set of points in the plane. IEEE Trans. Inf. Theory 29(4), 551–558 (1983)

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

Gansner, E.R., Hu, Y., Krishnan, S.: COAST: a convex optimization approach to stress-based embedding. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 268–279. Springer, Heidelberg (2013)

Gansner, E.R., Yifan, H., North, S.C.: A maxent-stress model for graph layout. IEEE Trans. Vis. Comput. Graph. 19(6), 927–940 (2013)

Gao, X., Xiao, B., Tao, D., Li, X.: A survey of graph edit distance. Pattern Anal. Appl. 13(1), 113–129 (2010)

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)

Hinton, G.E., Roweis, S.T.: Stochastic neighbor embedding. In: NIPS 2002, pp. 833–840 (2002)

Hu, Y., Koren, Y.: Extending the spring-electrical model to overcome warping effects. In: Eades, P., Ertl, T., Shen, H.-W. (eds.) PacificVis2009, pp. 129–136. IEEE (2009)

Huang, W., Hong, S.-H., Eades, P.: Effects of crossing angles. In: Fujishiro, I., Li, H., Ma, K. L. (eds.) IEEE PacificVis2008, pp. 41–46 (2008)

Jeh, G., Widom, J.: Simrank: a measure of structural-context similarity. In: KDD2002, pp. 538–543. ACM (2002)

Kobourov, S.G., Pupyrev, S., Saket, B.: Are crossings important for drawing large graphs? In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 234–245. Springer, Heidelberg (2014)

Marner, M.R., Smith, R.T., Thomas, B.H., Klein, K., Eades, P., Hong, S.-H.: GION: interactively untangling large graphs on wall-sized displays. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 113–124. Springer, Heidelberg (2014)

Nguyen, Q.H., Eades, P., Hong, S.-H.: On the faithfulness of graph visualizations. In: Carpendale, S., Chen, W., Hong, S. (eds.) PacificVis2013, pp. 209–216. IEEE (2013)

Preparata, F., Shamos, M.: Computational Geometry - An Introduction. Springer, New York (1985)

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

Purchase, H.C., Allder, J.-A., Carrington, D.A.: Graph layout aesthetics in uml diagrams: user preferences. J. Graph Algorithms Appl. 6(3), 255–279 (2002)

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

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

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

Tamassia, R., Batini, C., Di Battista, G.: Automatic graph drawing and readability of diagrams. Technical Report, Universita di Roma La Sapienza, Dipartimento do Informatica e Sistemistica, 01.87 (1987)

Tamassia, R., Batini, C., Talamo, M.: An algorithm for automatic layout of entity-relationship diagrams. In: Davis, C.G., Jajodia, S., Ng, P.A., Yeh, R.T. (eds.) ER83, pp. 421–439. North-Holland (1983)

Toussaint, G.: Computational Morphology. North Holland, Amsterdam (1988)

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

Wilkinson, L., Anand, A., Grossman, R.L.: Graph-theoretic scagnostics. In: Stasko, J., Ward, M.O. (eds.) InfoVis2005, p. 21. IEEE (2005)