Information Technology Reference
In-Depth Information
This last problem of optimal color assignment was also studied by Gansner
e
tal.[9]
andbyHu
e
t al. [12], in the context of coloring virtual maps to maximize the color
difference between neighboring regions. In these works, a set of
k
distinctive colors
are assumed to be given, with
k
the number of countries in the map. Maps were then
colored by an optimal permutation of the
k
colors. On the other hand, in this paper we
assume that the color space can be either continuous or discrete, and we select among
all colors in the color space to increase color differences. When applied to map coloring,
ouralgorithm produces
k
distinctive colors as a side product.
Dillencourt
e
tal.[7]studied the problem of coloringgeometric graphs so that colors
on nodes are as different as possible. The problem they studied is very related to ours,
except that in their case the application is the coloring of geometric regions, while we
are also interested in coloring edges of a graph. Dillencourt
e
tal.used a force-directed
gradient descent algorithm to find a
locally optimal
coloring of each node with regard to
its neighbors. We propose a new algorithm based on a branch-and-bound process over
an octree decomposition of the color space, that finds a
globally optimal
coloring for
each node with regard to its neighbors. Furthermore, our approach is more flexible and
works for discrete color palettes, in addition to continuous color spaces.
The angular resolution of a drawing is the sharpest angle formed by any two edges
that meet at a common vertex.In addition to maximizing crossing angles (e.g., [6]),
for the same reason of visual clarity, there have been researches to maximize the an-
gular resolution of the drawing. Most recently, Lombardi Drawing of graphs was pro-
posed [8,3], in which edges are drawn as arcs with perfect angular resolution. However,
Purchase
e
tal.[20]found that even though users prefer the Lombardi style drawings,
straight-line drawings created by a spring-embedder gives better performance for path
following and neighbor finding tasks. For straight-line drawings, while it is possible to
adjust the layout to improve the angular resolution (e.g., [5,11]), the extent to which this
can be done is limited. Althoughapreviousstudy by Purchase
e
t al. [19] did not find
sufficient support for maximizing angular resolution, we do find that when two edges
connected to the same node are almost on top to each other, it is difficult to tell whether
these are two edges or one. For this reason we consider such edges as in collision too.
We note that a nice way to follow an edge, or to find the neighbors of a node, is to
use interactive techniques such as “link sliding”and“bring & go” [17]. The algorithm
we propose is primarily aimed at disambiguating a static drawing displayed on screen
or on paper, it can nevertheless be used in conjunction with such interactive techniques.
Finally, we were made aware of the work of Jianu
e
t al. [16] after the completion
of this work. Jianu
e
t al. [16] proposed a similar idea of using colors to differentiate
edges. However there are multiple important differences between that work and ours.
The construction of dual collision graph is different: Jianu
e
tal.settheedgeweights
among all edges to be the inverse of either the intersection angle, or the edge distance
if the edges do not intersect, which is not optimal since it is perfectly harmless to color
edges that have no conflict with the same color. In fact, their method always results
in a complete collision graph, making it more expensive for relatively large graphs.
Furthermore, because of the complete collision graph, all edges of the original graph
must have different colors. Therefore the drawingsin[16],whichareallofverysmall
graphs, always contain a multitude of colors, which is unnecessary. Our collision graph
