Information Technology Reference
In-Depth Information
a static image on paper, or on screen. The motivation comes from users of the Graphviz
[10] software. These users were generally happy with the layouts of their graphs, but
were asking whether there was any visual instrument that can help them follow edges
better. Examining their layouts, we realized that because edges were drawn using the
same color (e.g., black), when there were a lot of edge crossings, it was difficult to vi-
sually follow these edges. Thus the feedback from our users, and our own observation,
echo the findingsbyHuang
e
t al. [14,15]. When explaining why small crossing angles
are detrimental to the task of following apath,theyfound, with the help of an eye track-
ing device, that
“when edges cross atsmall angles, crossingscause confusion,slowing
down andtriggering extra eye movements.”
and that
“in many cases, it is crossingsthat
cause confusion, making all thepathsbetween two nodes, andbranches along these
paths, unforeseeable. Duetothe geometric-path tendency, human eyes can easily slip
into theedges that are close to the geometric path but not part of thetarget path.”
.
Edge crossing is not the only hindrance to the visual clarity of a graph drawing.An
additional problem is that when an edge from node
u
passes underneath the label of a
node
v
and connects to a node
w
, it is impossible to tell visually whether there is one
edge
u
w
,whenalledges are of the same color (e.g.,
Fig. 3(b)). While these problems can be solved with user interactions by clicking on an
edge of interest, or on a node to bring its neighbors closer (see, e.g., [17]), this involves
an extra step for the user that may not be necessary if edges can be differentiated with
a proper visual cue. Furthermore, there are situations where interaction is not possible,
e.g., when looking at a static imageofagraph on screen, or in print. These are the
situations that are of particular interest in this paper.
We believe all the above mentioned problems of visually distinguishing and fol-
lowing edges can be greatly alleviated by choosing appropriate colors or line styles to
differentiate edges. We first identify edge pairs that need to be differentiated (the
collid-
ing edges
), and represent them as nodes of a dual collision graph. We then propose an
algorithm to assign colors to the nodes of this collision graph, in a way that maximizes
the color difference between nodes that share an edge. Thusour main contributions are:
-
A novel branch-and-bound graph coloring algorithm that finds the globally optimal
color embedding of each node with regard to its neighbors, and that works with
both continuous color spaces and discrete color palettes.
-
A user study that establishes the effectiveness/limitations of the coloring approach.
ₔ
w
,ortwoedges
u
ₔ
v
and
v
ₔ
2
Related Work
Graph coloring is a classic problem in algorithmic graph theory. Traditionally the prob-
lem is studied in a combinatorial sense. For example, finding the smallest number of
k
colors on the vertices of a graph so that no two vertices sharing an edgehavethesame
color. The difference between this and our work is that in
k
colorability problem, a
solution is valid as long as any pairs of vertices that share an edge have different colors,
no consideration is given to maximizing the actual color differences. So in essence, the
distance between colors is binary - either 0, or 1. For our problem we assume that even
among distinctive colors, the differences are not equal, and are measured by color dis-
tances. In the special case when only
k
colors are allowed, ouralgorithm degenerates to
find the optimal color assignment among all solutions of the
k
−
−
colorability problem.
