Mental map preservation principles and related measurements for quantitative evaluation of force-directed graph layout algorithm behaviour

Users working with graph layouts form mental maps of the layout’s parts and relative structure. When a graph layout is changed, the user’s mental map should be preserved. In the field of graph drawing, there is a need for quantitative and objective measurements to describe and compare layout algorithm behaviour as it pertains to maintenance of the mental map. This thesis presents several mental map preservation principles gathered from the literature, and generates related measurements that can be used to statistically characterize and test for significant differences between layout algorithm behaviour. Two well-known and similar Force-Directed layout algorithms (Kamada-Kawai and Fruchterman-Reingold) are compared, and the results show statistically significant differences. The measurements, statistics, and methodology presented in this thesis may be helpful to layout algorithm designers and graph layout system designers who want to be able to quantitatively and objectively test the algorithms on which they depend.