Information Technology Reference
In-Depth Information
Stephen C. North
Alejandro Estrella-Balderrama
Ye
Fabrizio Frati
Emden R. Gansner
Peter Eades
Patrizio Angelini
J. Joseph Fowler
Therese C. Biedl
Yifan Hu
David R. Wood
Cesim Erten
a Binucci
Stephen G. Kobourov
Maurizio Patrignani
Seok-Hee Hong
Giuseppe Di Battista
Christian A. Duncan
Sue Whitesides
G
urizio Pizzonia
David Eppstein
Fabrizio Frati
ni
Michael T. Goodrich
Maarten Loer
Walter Didimo
Giuseppe Liotta
Stephen K. Wismath
Nikola S. Nikolov
ara Mchedlidze
(a) clipping of an output with
l
unit
= 2cm
(b) clipping of an output with
l
unit
= 3cm
Fig. 4.
Output examples with different choices for
l
unit
the respective author and the weight of an edge connecting two authors is the num-
ber of their joint publications. We focusedonadrawing area of 29
.
7
cm
×
21
cm
(DIN
A4) where the size of vertices was determined by the author's name (in 10pt font). For
the complete publication graph, the runtimes were about2minutes, depending on the
parameters.
The main results of our tests are the following.
-
The preprocessing step described in Sec. 2.2 pays off; depending on the parameter
c
pre
,wemaysaveruntime and get better results. In ourtests,
c
pre
= 0
.
7 seemed a
good choice; see Table 1 in the extended version of the paper [2].
-
For testing whether something has to be removed, we set
l
adj
= 0
.
1
l
unit
and
l
nadj
=
0
.
15
l
unit
. For the parameter
c
len
that determines whether an edge or a vertex will
be removed,
c
len
= 0
.
9 gave a good compromise between the vertex and the edge
weight in the final drawing; see also Table 2 in the extended version [2].
-
We tested the effect of not always activating the force that repels vertices from
edges; instead, we first computed an equilibrium without the force and then another
one with it, so that we have more flexibility for vertices to cross edges. In our
tests, this proved to have a significant impact on the total weight of edges in the
final drawing, yielding an increase of almost 80%; see Table 3 in the extended
version [2].
-
The following way of computing the total force vector
F
for a vertex based on
putting weights to the single forces showed the best results:
F
= 0
.
01
F
r
+ 0
.
01
F
a
+
0
.
005
F
g
+ 0
.
0075
F
e
+ 0
.
01
F
f
. Note that not all forces are active at the same time.
A central parameter used in ouralgorithm is
l
unit
, describing the desired edgelength.
Figure 4 shows output examples that demonstrate that higher values lead to drawings
that are less dense. Full outputs are available in the extended version of the paper [2]
3
Calculation Graphs
We now consider the initial problem of drawing calculation graphs in prescribed area.
In our terminology, most of the input stays the same compared to general graphs, except
