Information Technology Reference
In-Depth Information
-
Existing methods do not scale well visually. A standard screen with a few megapix-
els cannot faithfully display graphs of a few million edges.
-
An underlying problem lies in the optimisation criteria for layoutalgorithms for
large graphs. For small scale graphs, criteria such as the number of edge cross-
ings have been successfully used and validated [13, 14]. However, all commonly
used algorithms for large graph layoutignore these criteria and generally use an
optimisation criterion based on a notion of energyorstress[4].
-
Readable large graphs might not be sufficient for understanding,asrequirements
differ based on the application and the task at hand. Moreover, the user can interac-
tively explore different regions of the graph which are not known in advance, e.g.
to compare or investigate the local structures, while keeping their global context.
This paper makes the contribution of a new interaction technique, GION, for ma-
nipulating layouts of large graphs. GION is novel by employing a physics engine to
simplify the process of interacting with large graphs, treating the graph as a set of con-
nected rigid bodies. The physics engine provides smooth animation for the user while
interactively laying outthegraph, and this animation improves the understanding for
the userofthegraphs underlying structure. When the user moves a cluster, the con-
nected clusters are also moved, as if they were connected in a chain. Our contribution
is validated with a user study conducted to evaluate the effectiveness of the technique
in a
graphuntangling
task.
The remainder of this paper is structured as follows. Section 2 describes previous
research related to this paper. Section 3 describes the details of the new graph interaction
technique. Section 4 outlines the user study conducted to evaluate the new interaction
technique, with the results presented in Section 5 followed by a discussion of these
results in Section 6. Finally, the paper concludes with a discussion of future work.
2
Background
While readability of graph drawings has been a topic of research for decades, and there
is a wealth of papers on the evaluation of drawing quality, e.g. [7, 13], the research has
focused mainly on task based performance for diagrams of small to medium size. Sev-
eral well established quality criteria for graph layouts exist. The most prominent one is
the number of crossings, which was verified to be an impediment for the human under-
standing of small graphs in empirical experiments [13]. Further well established quality
criteria are angular resolution, edgelength deviation, and stress. Recently, Huang et
al. [7] suggested that it is often better to make compromises between aesthetics, instead
of trying to satisfy one or two of them to the fullest. It has however not yet been in-
vestigated if the results obtained for small graphs can be extended to huge graphs or if
different quality criteria have to be employed.
Recently, Dwyer et al. [3] compared user-generated and automatic graph layouts,
where users were asked to optimize the layout for aesthetics and social network analysis
tasks. In their study, users that were asked to optimize a graph layout for an analysis task
used the term “untangling” to describe their process. In contrast the term “untangle”
here is not task related but used in a relatively informal sense: a user “untangles” a
graph drawing when they improve the layout, in the subjective opinion of the user. In
