Information Technology Reference
In-Depth Information
2.1
Our Algorithm
Our approach uses the force-directed framework; in this class of algorithms, the drawing
is incrementally improved, starting with an arbitrary layout. Each improvement step is
done by letting
forces
,definedusing physical analogies, move the vertices.
In contrast to usual force-directed algorithms, we have to take both the dimensions
of vertices and of the prescribed drawing area into account. Therefore, we add two
important ingredients: We try to fit the drawing into a frame of decreasing size, and we
remove vertices or edges from the graph in order to make the graph smaller so that the
current drawing can fit into the current frame. While, as a first idea, fitting the drawing
into the given area could be steered by a force pulling all vertices towards the center of
the drawing region, this idea has some drawbacks. Therefore, we will introduce a more
advanced approach. Similarly, removing vertices could simply be done by removing the
lightest vertex in each step. However, this would take neither the structure of the graph
nor the current drawing into account. Hence, we introduce a measure for the
stress
of
vertices in the current situation; we will always remove the vertex with the highest stress
value. In the following paragraphs, we will detail outouralgorithm's individual steps.
Forces.
We first define the forces usedinouralgorithm.
-
We r euse existing forces from the algorithm of Fruchterman and Reingold [10];
that is, for any pair
u
,
v
·
uv
on
v
that repels
v
from
u
,where
uv
is the unit vector pointing from
u
towards
v
.If
the vertices are adjacent, that is, if
uv
V
of vertices, there is a force
F
r
(
u
,
v
)=
l
unit
/
(
d
(
u
,
v
))
∈
E
, there is an additional force
F
a
(
u
,
v
)=
(
d
(
u
,
v
))
2
/
l
unit
·
vu
that attracts
v
towards
u
. Both forces use a factor
l
unit
which
describes the desired unit edgelength. Since the desired edgelength heavily influ-
ences the density of the drawing, and, hence, the number and weight of vertices
and edges that can be placed within the given drawing area, the choice of
l
unit
is
crucial for the results. While we allow the parameter to be set freely, we stress that
the valuemust be chosen carefully, taking the sizes of vertices into account, so that
one gets nice outputdrawings.
-
Due to the high density of the input graphs and the given sizes of vertices, it may
easily occur that vertices are intersected by nonincident edges, which reduces the
readability significantly. As a first step to overcome this problem, we use a force
that has been introduced by Bertault in his PrEd algorithm [3]: If an edge
∈
}
intersects a vertex
v
in its inner region, that is, close to the center of
v
,thenweleta
force
F
e
(
v
,
{
u
,
w
·
i
v
v
repel
v
from
d
(
v
,
i
v
))
2
, where the point
i
v
is
the orthogonal projection of
v
onto the straight-line segment
uw
. Note that this does
not guarantee that intersections between vertices and edges are avoided. However,
such intersections become less likely; in Sec. 2.2, we will see how their number can
be further reduced by routing edges as curves.
-
For making the drawing more compact, we introduce a force
F
g
(
v
)=
d
(
v
,
p
c
)
{
u
,
w
}
)=(
l
unit
−
{
u
,
w
}
·
−
vp
c
that attracts each vertex
v
to the center
p
c
of the drawing area. In our experiments it
turned out that activating this force in later steps of the algorithm reduces the time
for finding afinaldrawing,butalsothequality of the output. Therefore, as a default,
the force is only active when computing the very first equilibriumlayout.
