Information Technology Reference
In-Depth Information
b
a
Fig. 2.
Adrawing whose coordinates
cannot be computed by a quadratic
computation tree.
Fig. 1.
Two stable drawingsof
K
4
.
3
Impossibility Results for Force Directed Graph Drawing
In the Fruchterman and Reingold [4] force-directed model, each vertex is pulled toward
its neighbors with an attractive force,
f
a
(
d
)=
d
2
/k
,andpushed away from all vertices
with a repulsive force,
f
r
(
d
)=
k
2
/d
. The parameter
k
is a constant that sets the scale
of the drawing,and
d
is the distance between vertices. We say that a drawing is a
Fruchterman and Reingold equilibrium when the total force at each vertex is zero.
In the Kamada and Kawai [5] force-directed model, every two vertices are connected
by a spring with rest length and spring constant determined by the structure of the graph.
The total energyofthegraph is defined to be
E
=
i
2
k
ij
dist(
p
i
,p
j
)
ij
2
,
1
−
j>i
where
p
i
= position of vertex
v
i
,
d
ij
= graph theoretic distance between
v
i
and
v
j
,
L
= a scaling constant,
ij
=
Ld
ij
,
K
= a scaling constant, and
k
ij
=
K/d
i,j
.We
say that a drawing is a Kamada-Kawai equilibriumif
E
is at a local minimum. The
necessary conditions for such a local minimum are as follows:
k
ji
(
x
j
− x
i
)
1
−
=0
∂x
j
=
i
=
j
∂E
ji
dist(
p
j
,p
i
)
1
≤ j ≤ n
y
i
)
1
=0
∂y
j
=
i
=
j
∂E
ji
dist(
p
j
,p
i
)
k
ji
(
y
j
−
−
1
≤
j
≤
n.
For either of these approaches to force-directed graph drawing,agraph can have
multiple equilibria (Figure 1). In such cases, typically, one equilibrium is the “expected”
drawing of the graph and others represent undesired drawings that are not likely to be
found by the drawing algorithm. To make the positions of the vertices in this drawing
concrete, we assume that the constants
k
(Fruchterman-Reingold),
L
,and
K
(Kamada-
Kawai) are all equal to 1. As we will demonstrate, there exist graphs whose expected
drawings cannot be constructed in our models of computation. Interestingly, the graphs
we use for these results are not complicated configurations unlikely to arise in practice,
but are instead graphs so simple that they might at first be dismissed as insufficiently
challenging even to be used for debugging purposes.
