Information Technology Reference
In-Depth Information
use the LAB palette. In another half, the participants selected their favorite palette and
completed tasks with the colored drawings generated by this palette.
Data and Task.
Two lay outs of the Zachary's Karate Club Graph were used. One was
exactly the layoutinFig. 2. Another was rotated and re-labeled. Three types of graph-
related tasks were designed:
T1 (Connectivity):Determine whether two nodes are connected byadirect edge;
T2 (Neighbor): Estimate the number of nodes a particular node connects directly;
T3 (Path): Estimate the minimum number of hops fromaparticular node to another,
including thesource anddestination.
On each type, four tasks were selected on each graph layout with similar difficulty
levels. To eliminate user'svisual node querying time from their task completion time,
we annotated the related nodes in each task on the correspondinggraph layoutbefore
participants took the task.
Result.
Results were analyzed separately on each task type. Detailed analysis and
error bar charts are given in the technical report [13]. The major findingsarethaton
connectivity tasks, the average task error of the Color group is less than 30% of the
B/W group, and is statistically significant. Performance difference on neighbor/path
tasks and color palettes were not statistically significant.
6
Conclusions
Edge crossings, particularly those at small crossing angles, are known to be detrimental
to the visual understanding of graph drawings. This paper proposes an edge coloring al-
gorithm for disambiguating edges that are in collision because of small crossing angles
or partial overlaps. The algorithm, based on a branch-and-bound procedure applied to
a space decomposition of the color gamut, generates color assignments that maximize
color differences of the colliding edges, and works for both continuous color space and
discrete color palettes. The algorithm can also be applied to generate coloring for dis-
ambiguating virtual maps. Our user study found that coloring edges in graph drawings
helped user's performance in 1-hop graph connectivity task significantly. Consequently
we have made the CLARIFY code available as part of Graphviz open source software.
The approach of coloring edges for disambiguating drawings has its limitations. Our
working assumption is that the drawing is to be displayed as a static image on paper
or screen. When an interactive environment is available, techniques such as “link slid-
ing”and“bring & go” [17] could be more effective. In such a situation, the algorithms
proposed here can be used as an additional visual aid to the interaction.
While the algorithm proposed here can run on relatively large graphs, our experience
is that for graphs with a lot of edges, a static imageisinsufficient to allow the user to
clearly see and follow each edge. Therefore our approach is best suited for small- to
medium- sized graphs. Typical usage scenarios are illustrations of diagrams, such as
computer or biological networks.
Finally, we note that sometimes edge colors are used to encode attributes on the
edges. To apply our approach without interfering with the need to display such at-
tributes, edges can be differentiated using dashed lines of different style and/or thick-
ness, using CLARIFY through mapping different line styles to 1D or 2D spaces.
