Information Technology Reference
In-Depth Information
w
w
v
1
v
1
v
2
v
2
u
u
p
e
p
e
v
3
v
3
(a) Repelling forces
(b) Attracting forces;
v
3
is too far away for an attraction.
Fig. 3.
Repelling and attracting forces for Bezier curves
Postprocessing: Bezier Curves.
In Sec. 2.1, we explained the force that aims at avoiding
intersections between vertices and nonincident edges. However, we cannot guarantee
that we do not have such intersections. We can do two thingsabout this: (i) Intersections
of an edge with the outer region of a vertex are relatively easy to distinguish from
incidences and can, therefore, be tolerated. (ii) We can remove more edges if necessary.
Here, we present a third possibility: If we allow edges to be curves rather than
only straight-line segments, we can avoid more intersections. In their improvement to
Bertault's PrEd algorithm, Simonetto et al. [16] allowed polyline edges, where bends
are introduced and removed based on the current drawing. However, this approach made
the algorithm much slower; also, use a postprocessing in which edges are routed as
Bezier curves around intersected nonadjacent vertices. We do this by representing edge
e
=
by a quadratic Bezier curve, i.e., a parametric curve with a control point
p
e
in addition to the endpoints.
The computation of the curve is done as a postprocessing in the very last step of
the algorithm. It is realized as an additional force-directed algorithm in which only the
control point is moved, starting at the position in the middle between
u
and
w
. Each
vertex
v
that is not far away from
e
causes a repelling force on
p
e
;seeFig.3a.This
force is parametrized by the width
w
v
and the height
h
v
of
v
as well as by the point
p
v
of
v
that is closest to
e
and the point
p
e
of
e
that is closes to
v
. The repelling force is
defined as
F
rb
(
e
,
v
)=
−−ₒ
{
u
,
w
}
(
w
v
+
h
v
)
/
d
(
p
v
,
p
e
).
In order to avoid that the edgeiscurved too much, we also have an attracting force for
vertices that have been (almost) intersected by
e
.If
v
is such a vertex, then the attracting
force
F
ab
(
e
,
v
)=
−−ₒ
p
v
p
e
·
d
(
p
v
,
p
e
)
2
/
w
v
+
h
v
is applied to
p
e
;seeFig.3b.
p
e
p
v
·
2.3
Experiments and Evaluation
We implemented ourheuristic in Java, using the graph library JUNG[1]. Our experi-
ments were performed on a Core i5-2500K CPU with 8 GB of RAM. For the force-
directed part of the algorithm, we also used a cooling factor that slows down the move-
ment of vertices over the iterations in order to accelerate the computation of an equi-
librium. We configured ouralgorithm such that there are always 25 steps of shrinking
the frame around the current drawing.Asinput data, we primarily used (subgraphs of)
the graph drawing collaboration graph from 1994 till 2012; in total, the graph has 950
vertices and 2559 edges. The weight of each vertex is the number of publications of
