Information Technology Reference
In-Depth Information
also tend to exhibit a low perceptual complexity, making it relatively easy to follow
edges and paths. Compared with a non-mesh-like graph, a mesh-like graph is easier for
ouralgorithm because there are typically fewer colliding edges. We ran the experiment
on a Macbook Pro laptop with a 2.3 GHz Intel Core i7 processor.
Ta b l e 1 .
S
tatistics on the original and dual test graphs, CPU time (in second) and objective
function (cdiff) for CLARIFY. The time in bracket is for constructing the dual collision graph.
graph
|
V
| |
E
|
|
E
c
|
CPU iff
ngk 4
50
100
54
0.6 (0.)
122.69
NotreDame yeast 1458 1948
1685
1.3 (0.2)
67.9
GD00 c
638
1020
1847
1.7 (0.1)
64.32
Erdos971
429
1312
4427
2.1 (0.1)
59.3
Harvard500
500
2043 11972 2.3 (0.3)
35.0
extr1
5670 11405 34696 14.5 (7.9)
47.1
It can be seen from Table 1 that for graphs of uptoafewthousand nodes and edges,
CLARIFY runs quickly. The majority of the CPU time is spent on color assignment,
while the construction of the collision graph takes relatively little time even with the
naive dual graph construction algorithm. The Harvard500 graph gives a large
(num-
ber of edges in the collision graph) in comparison to the number of edges, because it has
a few almost complete subgraphs, which results in a lot of crossingsatsmallangles.
|
E
c
|
5
User Study
We conducted a controlled experiment to study the effect of edge coloring on user'sper-
formance in fundamental graph-related tasks, such as visually following edges, finding
neighbors and calculating the shortest path. Generally we compared two approaches,
defined as two visualization types: the baseline graph drawing in black-white (B/W)
and the improved graph drawing with edges colored by ouralgorithm (Color).
Experiment Design.
We recruited 12 participants (8 male, 4 female) for this paper-
and-pencil experiment. 10 of the participants were graduate students majoring com-
puter science and the other 2 of them were department assistants with no technology
background. Half of the participants had experiences on node-link graphs, one student
was even an expert on graphs. The other half did not have previous knowledge with
the node-link graph. The experiment followed a within-subject designwitheverypar-
ticipant doing all tasks with both visualization types. To eliminate the learning effect
over the same task, we used two different layouts of the same graph data. We had a full
factorial deign on the choice of two visualization types and two graph layouts. Each par-
ticipant entered the same task four times in total. The experiment order was randomized
across participants. Half of them completed the tasks first with the B/W approach and
then with the Color approach. Another half adopted the opposite order. Further, in half
of the time when participants were given the colored drawing,thealgorithm is fixed to
