A User Study in Similarity Measures for Graph Drawing

Bridgeman, Stina and Tamassia, Roberto (2001) A User Study in Similarity Measures for Graph Drawing. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 19-30 (Official URL: http://dx.doi.org/10.1007/3-540-44541-2_3).

Full text not available from this repository.


The need for a similarity measure for comparing two drawings of graphs arises in problems such as interactive graph drawing and the indexing or browsing of large sets of graphs. This paper builds on our previous work [3] by defining some additional similarity measures, refining some existing ones, and presenting the results of a user study designed to evaluate the suitability of the measures.

Item Type:Conference Paper
Additional Information:10.1007/3-540-44541-2_3
Classifications:M Methods > M.999 Others
M Methods > M.300 Dynamic / Incremental / Online
G Algorithms and Complexity > G.999 Others
D Aesthetics > D.001 General
ID Code:281

Repository Staff Only: item control page


T. Biedl, J. Marks, K. Ryall, and S. Whitesides. Graph multidrawing: Finding nice drawings without defining nice. In GD '98, volume 1547 of LNCS, pages 347-355. Springer-Verlag, 1998.

T. C. Biedl and M. Kaufmann. Area-efficient static and incremental graph darwings. In ESA '97, volume 1284 of LNCS, pages 37-52. Springer-Verlag, 1997.

S. Bridgeman and R. Tamassia. Difference metrics for interactive orthogonal drawing. J. Graph Alg. Appl. to appear.

S. S. Bridgeman, J. Fanto, A. Garg, R. Tamassia, and L. Vismara. Interactive Giotto: An algorithm for interactive orthogonal graph drawing. In GD '97, volume 1353 of LNCS, pages 303-308. Springer-Verlag, 1997.

E. Dengler and W. Cowan. Human perception of laid-out graphs. In GD '98, volume 1547 of LNCS, pages 441-443. Springer-Verlag, 1998.

E. Dengler, M. Friedell, and J. Marks. Constraint-driven diagram layout. In Proc. IEEE Sympos. on Visual Languages, pages 330-335, 1993.

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

U. Fößmeier. Interactive orthogonal graph drawing: Algorithms and bounds. In GD '97, volume 1353 of LNCS, pages 111-123. Springer-Verlag, 1998.

J. E. Goodman and R. Pollack. Multidimensional sorting. SIAM J. Comput., 12(3):484-507, Aug. 1983.

K. A. Lyons, H. Meijer, and D. Rappaport. Algorithms for cluster busting in anchored graph drawing. J. Graph Algorithms Appl., 2(1):1-24, 1998.

A. Marzal and E. Vidal. Computation of normalized edit distance and applications. IEEE Trans. on Pattern Analysis and Machine Intelligence, 15(9):926-932, Sept. 1993.

K. Misue, P. Eades, W. Lai, and K. Sugiyama. Layout adjustment and the mental map. J. Visual Lang. Comput., 6(2): 183-210, 1995.

S. North. Incremental layout in DynaDAG. In GD'95, volume 1027 of LNCS, pages 409-418. Springer-Verlag, 1996.

A. Papakostas, J. M. Six, and I. G. Tollis. Experimental and theoretical results in interactive graph drawing. In GD '96, volume 1190 of LNCS, pages 371-386. Springer-Verlag, 1997.

A. Papakostas and I. G. Tollis. Interactive and orthogonal graph drawing. IEEE Trans. Comput., C-47(11):1297-1309, 1998.

K. Ryall, J. Marks, and S. Shieber. An interactive system for drawing graphs. In GD '96, volume 1190 of LNCS, pages 387-393. Springer-Verlag, 1997.

R. Tamassia, G. Di Battista, and C. Batini. Automatic graph drawing and readability of diagrams. IEEE Trans. Syst. Man Cybern., SMC-18(1):61-79, 1988.

W. A. Wickelgren. Cognitive Psychology. Prentice-Hall, Inc., Englewood Cliffs, NJ, 1979.