Information Technology Reference
In-Depth Information
19
19
6
6
2
2
1
1
12
9
10
12
9
10
15
14
15
14
8
8
5
5
13
13
4
4
20
7
20
7
18
18
16
16
11
11
17
17
3
3
Fig. 1.
L
eft: a graph with 20 nodes and 100 edges. It is difficult to follow some of the edges.
For example, is node 19 (blue) connected to node 16 (blue)? Is node 19 connected to 17 (blue)?
Right: the same graph, with the edges colored using ouralgorithm. Now it is easier to see that 19
and 16 are connected by a blueedge, but 19 and 17 are not connected.
C3 could create confusion as to whether the two edges connected at close to 180 de-
gree are one edge, or two edges, when node labels are drawn. For example in Fig.1(left),
it is difficult to tell whether nodes 19 and 17 are connected, or whether 19 is connected
to 20 and 20 is connected to 17. When edges are properly colored (Fig. 1 (right)), it is
clear that the latter is true. Note that if edges are allowed to be drawn on top of nodes,
then an edge between 19 and 17 would be seen over the label of 20, thusthiskindof
confusion can be eliminated. Therefore we consider C3 as optional. Butdrawing edges
over the label of nodes introduce extra clutter and make the node labels harder to read.
C4 causes a problem because when two edges are very close and almost parallel, it
is difficult to differentiate between them. In addition, it can cause confusion when node
labels are drawn. Fig. 3(a) shows two lines very close and almost parallel. While it is
possible to differentiate between the two edges, when node labels are added (Fig. 3(b)),
it is difficult to tell whether there are two edges (1
ₔ
2and3
ₔ
4), or three edges
(1
ₔ
2, 1
ₔ
4and1
ₔ
3), or whether there even exists an edge3
ₔ
2. This confusion
can be avoided if suitable edge coloring is applied (Fig. 3(c)).
To resolve these collisions, we propose to color the edges so that any two edges in
collision have as different colors as possible. We first construct a dual edge collision
graph.
3.2
Constructing the Dual Collision Graph
Let the original graph be
G
=
{
V
,
E
}
. Denote by
N
(
v
) the set of neighbors of a node
v
.The
dual collisiongraph
is
G
c
=
, where each node in
V
c
corresponds to an
edge in the original graph. In other words, there is a one-to-one mapping
e
:
V
c
ₒ
{
V
c
,
E
c
}
E
.
Two nodes of the collision graph
i
and
j
are connected if
e
(
i
) and
e
(
j
) collide in the
original graph.
