Empirical evaluation of aesthetics-based graph layout

Many automatic graph layout algorithms have been designed and implemented to display relational data in a graphical (usually node-arc) manner. The success of these algorithms is typically measured by their computational efficiency and the extent to which they conform to aesthetic criteria (for example, minimising the number of crossings, maximising symmetry). Little research has been performed on the usability aspects of such algorithms: do they produce graph drawings that make the embodied information easy to use and understand? Is the computational effort expended on conforming to the assumed aesthetic criteria justifiable with respect to better usability? This paper reports on usability studies that were performed to investigate the merit of automatic graph layout algorithms with respect to human use. The paper describes three ways in which this issue has been considered experimentally: First, investigating individual aesthetic criteria in simple, abstract graph structures; second, investigating the results of common automatic graph layout algorithms; and third, investigating individual aesthetic criteria and other relevant secondary notations in Unified Modeling Language class and collaboration diagrams. The results show that the use of only some aesthetics affect usability significantly, and that the semantic domain of the graph drawings affects which aesthetic criteria need to be emphasised.