Comparaison de la lisibilité des graphes en représentation noeuds-liens et matricielle

ABSTRACT

This article describes a taxonomy of tasks on graphs and a controlled experiment for assessing the readability of two graph representations: matrices and node-link diagrams. The experiment only concerned a subset of the described tasks but provides important insights on the use of representations depending on the graph sizes and densities. It shows that, for graphs larger than 20 nodes or sufficiently dense, most tasks are performed more efficiently on the matrix-based representation. Only some path related tasks score better on node-link diagrams.

REFERENCES

• 1: 1. AT & T Labs Research. Graphviz - open source graph drawing software, 2004.
• 2: 2. Battista, G.D., Eades, P., Tamassia, R. and Tollis, I.G. Graph Drawing. Prentice Hall, 1999.
• 3: Richard A. Becker , Stephen G. Eick , Allan R. Wilks, Visualizing Network Data, IEEE Transactions on Visualization and Computer Graphics, v.1 n.1, p.16-28, March 1995 [doi>10.1109/2945.468391]
• 4: 4. Bertin, J. Sémiologie graphique : Les diagrammes - Les réseaux - Les cartes. Editions de l'Ecole des Hautes Etudes en Sciences, Paris, France, 1967.
• 5: Robert F. Cohen , Peter Eades , Tao Lin , Frank Ruskey, Volume upper bounds for 3D graph drawing, Proceedings of the 1994 conference of the Centre for Advanced Studies on Collaborative research, p.11, October 31-November 03, 1994, Toronto, Ontario, Canada
• 6: Mohammad Ghoniem , Jean-Daniel Fekete, Visualisation de graphes de co-activité par matrices d'adjacence, Proceedings of the 14th French-speaking conference on Human-computer interaction (Conférence Francophone sur l'Interaction Homme-Machine), p.279-282, November 26-29, 2002, Poitiers, France [doi>10.1145/777005.777054]
• 7: 7. Gottsdanker, R. Experimenting in Psychology. Prentice-Hall, 1978.
• 8: 8. Ham, F.v., Using Multilevel Call Matrices in Large Software Projects. in Proc. IEEE Symp. Information Visualization 2003, (Seattle, WA, USA, 2003), IEEE Press, 227-232.
• 9: Ivan Herman , Guy Melançon , M. Scott Marshall, Graph Visualization and Navigation in Information Visualization: A Survey, IEEE Transactions on Visualization and Computer Graphics, v.6 n.1, p.24-43, January 2000 [doi>10.1109/2945.841119]
• 10: Helen C. Purchase, The Effects of Graph Layout, Proceedings of the Australasian Conference on Computer Human Interaction, p.80, November 29-December 12, 1998
• 11: Helen C. Purchase , David Carrington , Jo-Anne Allder, Empirical Evaluation of Aesthetics-based Graph Layout, Empirical Software Engineering, v.7 n.3, p.233-255, September 2002 [doi>10.1023/A:1016344215610]
• 12: H. C. Purchase , R. F. Cohen , M. I. James, An experimental study of the basis for graph drawing algorithms, Journal of Experimental Algorithmics (JEA), 2, p.4-es, 1997 [doi>10.1145/264216.264222]
• 13: Colin Ware , Helen Purchase , Linda Colpoys , Matthew McGill, Cognitive measurements of graph aesthetics, Information Visualization, v.1 n.2, p.103-110, June 2002 [doi>10.1057/palgrave.ivs.9500013]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Evaluation/methodology

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Representations, data structures, and transforms
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Ergonomics; Interaction techniques

General Terms:
Design

Keywords:
adjacency matrices, evaluation, node-link representation readability, visualization of graphs