Information Technology Reference
In-Depth Information
almost always contains disconnected components.This decomposes the coloring prob-
lem into smaller ones, and allows ustouse the same (black) colors for many edges.
Jianu et al. [16] solved the coloring problem using a force-directed algorithm, moti-
vated by Dillencourt
e
t al. [7]. We were kindly given the source code for [16] from one
of the authors. Based on reading thecode,wefound that it applies force directed algo-
rithm to nodes of the collision graph in the 2D subspace of the LAB color space (the
AB subspace). It then sets a fixed L valueof75(Listhelightness, between 0 to 100).
This observation is consistent with the drawings in [16], where black background is
used for all drawingsdue to the highlightness value(seealsoFig. 5(d)). This makes the
algorithm limited to a small subset of all possible colors. Finally, the force-directed al-
gorithms of Dillencourt
e
tal.[7]andJianu et al. [16] can only be applied to continuous
color space in 2D or 3D. Neither works for user specified color palettes, or 1D colors.
Ouralgorithm works for both continuous or discrete color spaces. Overall, we believe
that the idea of using colors for disambiguating edges are quite natural to think of. It is
how to design appropriate algorithms to make the idea work effectively in practice that
is crucial and that differentiates our work and [16]. Furthermore, we present a first user
study to evaluate results of ouralgorithm with real users. The results suggest possible
scenarios when ouredge coloring approach is effective.
3
The Edge Coloring Problem and a Coloring Algorithm
Appropriate coloring can help greatly in differentiating edges that cross at a small angle.
Fig. 1 (left) illustrates such a situation. With many crossing edges, it is difficult to follow
the edge from node 19 (top-middle, blue) to node 16 (lower-right, blue). In comparison,
in Fig. 1 (right), it is easier to see that 19 is connected to 16 by a blueedge. The objective
of this section is to identify situations where ambiguities in following edges can occur,
and propose an edge coloring algorithm to resolve such ambiguities.
3.1
Edge Collisions
Two edges are considered in collision if an ambiguity arises when they are drawn using
the same color. The following are four conditions for edge collision:
-
C1: they cross at a small angle.
-
C2: theyare connected to thesame node at a small angle.
-
C3 (optional): theyare connected to thesame node at an angle close to 180 degree.
-
C4: they do not cross or share anode, but are very close to each other and are
almost parallel.
We now explain the rationale for considering each of these four conditions as being
in collision. C1 is considered a collision following the user studies described in Sec-
tion 1 by Huang
e
t al. [14,15]. When eyes try to follow an edge to its destination, small
crossing angles between this edge and other edges create multiple paths along the di-
rection of the eye movement, either taking eyes to the wrong path, or slowing down
the eye movement. C2 creates a situation where one edge is almost on top of the other,
making it difficult to visually follow one of these edges.
