An experimental study of the basis for graph drawing algorithms

ABSTRACT

Designers of graph drawing algorithms and systems claim to illuminate application data by producing layouts that optimise measurable aesthetic qualities. Examples of these aesthetics include symmetry (where possible, a symmetrical view of the graph should be displayed), minimise arc crossing(the number of arc crossings in the display should be minimised), and minimise bends (the total number of bends in polyline arcs should be minimised).The aim of this paper is to describe our work to validate these claims by performing empirical studies of human understanding of graphs drawn using various layout aesthetics. This work is important since it helps indicate to algorithm and system designers what are the aesthetic qualities most important to aid understanding, and consequently to build more effective systems.

REFERENCES

• 1: Carlo Batini , L. Furlani , Enrico Nardelli, What is a Good Diagram? A Pragmatic Approach, Proceedings of the Fourth International Conference on Entity-Relationship Approach, p.312-319, October 29-30, 1985
• 2: BHANJI, S., PURCHASE, H., COHEN, a., AND JAMES, M. 1995. Validating graph drawing aesthetics: A pilot study. Technical Report 336, University of Queensland Department of Computer Science.
• 3: Chen Ding , Prabhaker Mateti, A Framework for the Automated Drawing of Data Structure Diagrams, IEEE Transactions on Software Engineering, v.16 n.5, p.543-557, May 1990 [doi>10.1109/32.52777]
• 4: EADES, P. 1984. A heuristic for graph drawing. <i>Congressus Numerantium 42</i>, 149-160.
• 5: FERRARI, D. AND MEZZALIRA, L. 1969. On drawing a graph with the minimum number of crossings. Technical Report 69-11, Istituto di Elettrotecnica ed Elettronica, Politecnico di Milano.
• 6: M. Formann , T. Hagerup , J. Haralambides , M. Kaufmann , F. T. Leighton , A. Symvonis , E. Welzl , G. Woeginger, Drawing graphs in the plane with high resolution, SIAM Journal on Computing, v.22 n.5, p.1035-1052, Oct. 1993 [doi>10.1137/0222063]
• 7: Ashim Garg , Roberto Tamassia, Planar Drawings and Angular Resolution: Algorithms and Bounds (Extended Abstract), Proceedings of the Second Annual European Symposium on Algorithms, p.12-23, September 26-28, 1994
• 8: GOTTSDANKER, a. 1978. <i>Experimenting in Psychology</i>. Prentice-Hall.
• 9: R. J. Lipton , S. C. North , J. S. Sandberg, A method for drawing graphs, Proceedings of the first annual symposium on Computational geometry, p.153-160, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323254]
• 10: Gerald L. Lohse , Kevin Biolsi , Neff Walker , Henry H. Rueter, A classification of visual representations, Communications of the ACM, v.37 n.12, p.36-49, Dec. 1994 [doi>10.1145/198366.198376]
• 11: PURCHASE, H. AND LEONARD, D. 1996. Graph drawing aesthetic metrics. Technical Report 361, University of Queensland Department of Computer Science.
• 12: SIEGEL, S. 1956. <i>Nonparametric Statistics for the Behavioral Sciences</i>. McGraw-Hill.
• 13: Roberto Tamassia, On embedding a graph in the grid with the minimum number of bends, SIAM Journal on Computing, v.16 n.3, p.421-444, June 1987 [doi>10.1137/0216030]
• 14: Howard Trickey, Drag: a graph drawing system, Proceedings of the International Conference on Electronic Publishing on Document manipulation and typography, p.171-182, May 1988, Nice, France
• 15: V Vijayan, Geometry of planar graphs with angles, Proceedings of the second annual symposium on Computational geometry, p.116-124, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10528]
• 16: Colin Ware , David Hui , Glenn Franck, Visualizing object oriented software in three dimensions, Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: software engineering, October 24-28, 1993, Toronto, Ontario, Canada

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

Keywords:
human-computer interaction