Information Technology Reference
In-Depth Information
Handling theFrame.
The forces described above yield a functional force-directed algo-
rithm which can be applied for getting an initial layout. Once we have an initial drawing,
we initialize the frame
F
as the bounding box of the drawing.Ouralgorithm iteratively
reduces the size of the frame until it matches the prescribed drawing area.
In each step, we first uniformly reduce the height and the width of
F
by a small
amount. It may happen that some vertices (partially) lie outside of the resulting new
frame
F
. If this is the case for a vertex
v
,wejust place it at the closest position that lies
completely within
F
. This operation can result in intersections of vertices. Therefore,
we compute a new equilibrium state which hopefully solves the intersections.
In all force-directed iterations in which there is a frame, we will always ensure that
no vertex leaves the frame. This is done by cutting off the resulting movement vectors;
Fruchterman and Reingold [10] did the same for ensuring that no vertex leaves the
drawing area in their algorithm—with the difference that they did not shrink the frame
but rather started with a very compressed drawing since in their setting vertices are
points that can be arbitrarily close.
If there are intersections after computing anewequilibriumlayout, we have a clear
indication that the graph is still too largeforthecurrent frame and, hence, for the desired
drawing area. In this case, and also in some more cases, we will remove vertices or
edges as described in the next section.
Removing Vertices andEdges.
Our indicator for the necessity of the removal of vertices
or edges is, roughly speaking, the density of the drawing. If there are too many vertices
in the graph for the current frame, then vertices will come very close. Therefore, we de-
cide to remove a vertex or an edge if the minimumedgelength is less than a value
l
adj
or if the minimum distance between two nonadjacent vertices is less than a value
l
nadj
.
Note that this includes the case of two intersecting vertices.
Deciding what should be removed is more difficult. Since we want to keep as much
weight as possible, the natural idea is to remove the lightest vertex. However, this is
often not the best choice—even if it is unambiguous. A more advanced criterion should
take also the degree of a vertex into account. The higher the number of neighbors of a
vertex is, the more information on the graph is lost by removing the vertex.
Stress Calculation.
However, we can still do better: So far, the current drawing is not
taken into account, although it yields valuable information about the density of vertices
in the vicinity of the vertex that should be removed. Thus, we suggest considering the
forces in the last equilibriumlayout. Even if the total movement vector of a vertex has
length zero, this may actually result from strong forces that try to move the vertex to
different directions, e.g., if the vertex is “trapped” between many other vertices.
These considerations lead us to a measure that we call the
pressure
of a vertex. In-
tuitively, the pressure is the maximumstrength of forces in roughly opposite directions
that act on a vertex. For formalizing this, we subdivide all force vectors applied on the
vertex
v
into eight octants. For each octant, we sum up the force vector. For
i
= 0
,...,
7
let
l
i
be the length of the resulting force vector for octant
i
.Now,wefirstbuild the pres-
sure
p
i
for octant
i
by comparing
l
i
with the force vectors in the three opposite directions,
i.e., with
l
i
+3
,
l
i
+4
,and
l
i
+5
(mod 8); see Fig. 2. The pressure then is the maximum over
