Information Technology Reference
In-Depth Information
These findings have made the area of crossing minimization one of the most active
research topics in the graph drawing community; see [3] for an excellent survey. How-
ever, the problem of crossing minimization is computationally hard [9], and it remains
hard even when restricted to special graphs [11]. In fact, one cannot even compute in
polynomial time a crossing-optimal solution for a graph obtained from a planar one
by adding asingle edge [4]. Given that the problem is difficult, several heuristics have
been designed. The heuristics are usually hard to implement and they do not scale well
with the size of a graph [3]. Hence, it is a reasonable question to ask to what extent one
should try to minimize edge crossingstojustify the cost.
Other graph aesthetics have also been considered. Huang et al. [14] study crossing
angles (the minimumangle between pairs of crossing edges) and conclude that larger
crossing angles make graphs easier to read. This motivates the research area of right-
angle-crossing (RAC) drawings, where the goal is to make all crossing angles close to
90 degrees. Several studies consider the relative importance of various aesthetic criteria,
which is relevant as some of them can be conflicting (e.g., minimizing crossingsinpla-
nar graph drawings usually results in poor angular resolution). Huang and Huang [13]
argue that the number of edge crossings is relatively more important than the crossing
angles.
Alternative representations of large graphs and networks have also been considered.
Archambault et al. [1] show that coarseninggraph representations, in which several in-
terconnected vertices are merged into metanodes, does not result in significant improve-
ments over node-link diagrams. However, such representations might be beneficial for
specific tasks in very dense graphs. Jianu et al. [16], and Saket et al. [22] investigate
several methods of representing cluster information in large graphs. Their results indi-
cate that classical node-link diagrams are not the most efficient way to visualize large
clustered datasets.
3
Experiments
Objectives.
We conduct a controlled experiment to explore how edge crossings affect
the understandability of graph layouts. Although several studies assess the impact of
crossings, a number of important questions remain open. Our specific objectives are:
1. to confirm the results of prior studies that increasing the number of edge crossings
negatively impacts the usability of node-link diagrams for
small graphs
;
2. to verify whether increasing the number of edge crossingsalsonegatively impacts
the usability of node-link diagrams for
large graphs
;
3. to explore the impact of edge crossings while varying the
edge density
for both
largeandsmallgraphs;
4. to analyze the impact of edge crossingson
different tasks
.
Controlled experiments in graph drawing often involve manually creating different
layouts of the same graph, by varying only one aesthetic, while the others are kept
unchanged. However, duetothecomputational hardness of the crossing minimization
problem, and the use of larger graphs than those in previousstudies, it is almost impossi-
bletodothisinour setting. Instead we use a different approach to accomplish a similar
