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

Are Crossings Important for Drawing Large Graphs?

Stephen G. Kobourov 1 ,Sergey Pupyrev 1 , 2 , and Bahador Saket 1

1

Department of Computer Science, University of Arizona, Tucson, Arizona, USA

2

Institute of Mathematics and Computer Science, Ural Federal University, Russia

Abstract. Reducing the number of edge crossings is considered one of the most
important graph drawing aesthetics. While real-world graphs tend to be largeand
dense, most of the earlier work on evaluating the impact of edge crossings utilizes
relatively small graphs that are manually generated and manipulated. We study
the effect on task performance of increased edge crossingsinautomatically gen-
erated layouts for graphs, from different datasets, with different sizes, and with
different densities. The results indicate that increasing the number of crossings
negatively impacts accuracy and performance time and that impact is significant
for small graphs but not significant for large graphs. We also quantitatively eval-
uate the impact of edge crossings on crossing angles and stress in automatically
constructed graph layouts. We find a moderate correlation between minimizing
stress and the minimizing the number of crossings.

1 Introduction

Graphs are often used to model a set of entities and their relationships. They are usu-
ally visualized with node-link diagrams, where vertices are depicted as points and
edges as line-segments connecting the corresponding points. Many different methods
for drawinggraphs have been developed and they typically aim to optimize one or
more aesthetic criteria . According to the seminal work of Purchase [20], aesthetic
criteria include: number of edge crossings, number of edge bends, symmetry of the
drawing,angular resolution, crossing angles, and vertex distribution. Such criteria are
often proposed based on human intuition and the personal judgement of algorithm de-
signers, and therefore the task of validatinggraph drawing aesthetics is of high impor-
tance.
A great deal of the prior experimental evaluations of graph drawing aesthetics utilize
relatively small and nearly planar graphs and networks. For example, Purchase et al. [21]
conduct a user study with graphs on 16 vertices and 18 28 edges. Huang et al. [13, 14]

generate graphs having between 10 and 40 vertices. Larger graphs with 50 vertices are
used by Dwyer et al. [5] butthenumber of edges is only 75,whichresults in graphs
with almost tree-like structure. Real-world graphs, however, tend to be large, dense, and
non-planar.
There are several of-the-shelf methods for drawing large graphs. Classical force-
directed methods such as Fruchterman-Reingold [7] and Kamada-Kawai [17], and more
recent multiscale variants [10, 12], define and minimize the “energy” of the layout;
layouts with minimal energy tend to be aesthetically pleasing and to exhibit symme-
tries. Similarly, methods based on multidimensional scaling (MDS) minimize a partic-
ular energyfunction of the layout, called “stress” [8]. Note that the classical methods

−