Are Crossings Important for Drawing Large Graphs? - Graph Drawing - page 243

9600
9500
9400
9300
9200
9100
9000

9600
9500
9400
9300
9200
9100
9000

90000 95000 100000 105000 110000 52 54 56 58 60

number of crossings
(a) r (En , Cr) = 0 . 81

average crossing angle
(b) r (En , Ang) = − 0 . 27

Fig. 3. Relationship between the energy of the drawing (stress) and (a) the number of crossings,
(b) the average crossing angle. Dots represent values of the aesthetics computed for different
layouts created by the multidimensional scaling algorithm for the Recipes graph.

On the other hand, there are no strong correlations between the other aesthetics. Our
results indicate that the number of crossings and the crossing angles are independent in
the layouts created by the two evaluated algorithms. We also note a negative correlation
between the average crossing angle and the energyon4 graphs processed with the
MDS-based layoutalgorithm.

5 Conclusion and Future Work

All relevant materials for this study, including more detailed data analysis, are available
at http://sites.google.com/site/gdpaper2014 .
Our experimental results hopefully serve to inform designers of graph drawing algo-
rithms that minimizing the number of edge crossingsinlarge graphs is not as important
as in small graphs. The correlation between low energylayouts and layouts with few
crossings indicates that traditional energy-based methods might already result in some
reduction in crossings. Although we attempted to be as diverse as possible, ourresults
should be interpreted in the context of the specified graphs, sizes, densities, and tasks.
Duetonatural limitations (e.g., length and complexity of experiments), we could not
include graphs with more than 120 vertices and density greater than 2 . 5. Obtaining more
results for larger range of the parameters would hopefully help provide a more com-
plete picture. In our experiment we only considered relational reading of static graph
drawings; results may be different in experiments that require an interpretive reading of
graph drawings in the context of application domains. It would be also worthwhile to
consider tasks beyond the network-topology category.
Another interesting direction would be to study in depth the effect of layoutenergy
on understandability of graphs. Different energyfunction formulations (e.g., stress, dis-
tortion) likely have different impact. Evaluating such impact on a greater number of
quantitatively measurable aesthetic criteria, as well as on actual tasks performance, is
also a promising direction for future work.

Acknowledgements. The work supported in part by NSF grants CCF-1115971 and
DEB-1053573.