An Experimental Study of the Basis for Graph Drawing Algorithms

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 crossings (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. Categories and Subject Descriptors: 1.3 [Computer Graphics]: Picture/Image Generation— Display algorithms; H.5 [Information Interfaces and Presentation]: User Interfaces—Evaluation.