Information Technology Reference
In-Depth Information
are not designed to directly optimize a specific graph drawing aesthetic criterion. Yet
minimizing edge crossings remains the most cited and the most commonly used aes-
thetic [13, 15, 20, 21, 23]. With this in mind, we consider
theimpact of edge crossingson
thereadability of graphsinautomaticallygenerated straight-linelayouts of real-world
large graphs
.
Many real-world graphs (e.g., biological networks, social networks, research cita-
tion graphs) have tens of thousands or even millions of vertices. Such graphs are not
usually explored with static node-link diagrams, but rather with alternative visualiza-
tion methods based on interaction, abstraction, overview-detail views, etc [1, 16]. Still,
static node-link diagrams with more than a hundred vertices are common today. We
would like to determine a reasonable upper limit on the size of a graph, for which typ-
ical tasks can be performed using a static node-link diagram. In order to empirically
define the notion of a “large graph” in this setting,werun a preliminary experiment
with graphs on 100-150 vertices. For graphs with 150 vertices and density (the number
of edges divided by the number of vertices) of 3
.
5, task accuracy is steadily below 39%,
even in the most advantageous setting (e.g., highresolution display, unlimited time, the
simplest path-finding tasks, graph layouts with close-to-optimal number of edge cross-
ings, etc). The results of this preliminary experiment helped us determine usefulranges
of size and density of the graphs used in our main experiment. In the main experi-
ment, we consider
small
(40 vertices) and
large
(120 vertices) graphs. The graphs are
constructed from two real-world datasets and drawn with the classical force-directed
and MDS-based algorithms. We vary edge density (from 1
.
5 to 2
.
5)andthenumber
of crossings (by a factor of two), and analyze accuracy and completion time for four
tasks, frequently utilized in prior experiments. We also quantitatively evaluate the re-
lationship between edge crossings and several other layoutquality measures. Thusour
contributions are two-fold:
1. We measure accuracy and completion time for four graph tasks to evaluate the
effect of edge crossingsonsmallandlarge graphs with varying densities. The ex-
periments indicate that increasing the number of crossingshasanegative impact,
but the change is not significant for large graphs.
2. We quantitatively evaluate the impact of edge crossings on crossing angles and
stress in automatically constructed graph layouts. We find a moderate correlation
between minimizing stress and minimizing the number of edge crossings.
2
Related Work
Several empirical studies aim to determine the impact of various aesthetic criteria on hu-
man understanding of graph visualizations. A series of experiments by Purchase shows
that many of the aesthetics are indeed important [20]. The experiments indicate that the
number of edge crossings is by far the most important aesthetic, while the number of
edge bends and the local symmetry displayed have a lesser impact. These results are
confirmed by Huang et al. [15], who found that edge crossingssignificantly impact user
preference and task performance. Overall, it is a common belief that minimizing the
number of edge crossings is one of the most important goals in drawinggraphs.
