Information Technology Reference
In-Depth Information
{
{
p
i
,
p
i
+3
}
,
min
{
p
i
,
p
i
+4
}
,
min
{
p
i
,
p
i
+5
}}
the pairwise minima, i.e.,
p
i
= max
min
.The
{
p
0
,...,
p
7
}
total pressure on
v
is
p
(
v
)=max
.
Now, we must integrate the weight
w
(
v
) and the de-
gree deg(
v
)—indicators of the vertex's resistance against
pressure—with the pressure in order to get the
stress s
(
v
).
We do so by setting
s
(
v
)=
p
(
v
)
/
(
w
(
v
)
i
+3
i
+4
i
+5
(deg(
v
)+
c
deg
)).
Here,
c
deg
is a small positive constant that ensures that we
do not get problems for isolated vertices and that steers
our preference for keeping isolated vertices in the drawing.
With this definition of the stress, we can always choose the
vertex with the highest stress for removal.
·
v
i
Fig. 2.
Pressure computation
for one of the octants
Boundary Vertices.
There is a special case for vertices
close to the boundary of the frame. We never move a ver-
tex over the boundary although, in many cases, vertices are repelled in this direction by
the inner vertices. This phenomenon is a cause of pressure on a vertex that is, so far, not
covered by our definition. We therefore introduce a new “virtual” force that mimics the
resistance against movements that push the vertex out of the frame. This force repels
the vertex perpendicularly to the inside of the frame, away from the closest point
p
f
of the frame'sboundary. More precisely, the virtual force is
F
f
(
v
)=
−
p
f
v
l
unit
/
d
(
v
,
p
f
).
We stress that
F
f
is only taken into account for the stress computation and not actually
applied.
·
Edges.
In some cases, one may try to remove only an edge instead of a whole vertex;
the hope is that after removing the edge, the graph becomes more flexible so that the
available space can be used better. As an indicator for such a situation, we use the
averageedgelength in the current drawing.Ifthislength is larger than
l
unit
·
c
len
, with a
factor
c
len
>
0, we decide for removing an edge instead of a vertex. The intuition is that,
on average, the edges are not very short, which means that by removing one of these
longer edges we could allow more flexibility to the placement of vertices.
In order to determine which edge will be removed, we, again, use a definition of
stress. To this end, we take both the weight
w
(
e
) and the weights of the edges crossing
e
into account. Let
E
be the set of these edges. Then, we set
s
(
e
)=
∑
e
∈
E
w
(
e
)
E
|
·|
/
w
(
e
)
to be the stress of
e
, and we remove the edge with the highest stress value.
2.2
Extensions
We developed and implemented two extensions that can help improve the runtime of
the algorithm and the quality of the resulting drawings, respectively.
Preprocessing.
In many input instances, there is a largenumber of vertices with very
small weight, for which it is very unlikely to occur in the final drawing. To speed up
the algorithm, we can remove all vertices that are lighter than a threshold value
w
.
Our choice of
w
is based on guessing abound on the maximumnumber of vertices in
the final drawing and depends on the height
H
and the weight
W
of the drawing area,
the minimumheight
h
min
and the minimum width
w
min
of a vertex as well as on the
desired edgelength
l
unit
and a factor
c
pre
>
0. We will make sure that we keep at least
(
H
W
)
/
(
l
unit
c
pre
+
h
min
)
(
l
unit
c
pre
+
w
min
)
vertices in the graph.
·
·
