Information Technology Reference
In-Depth Information
3
40
23
45
1
10
19
40
29
40
3
13
(
40
+
40
)
4
5
21
40
3
13
4
40
(3+1)
(8+5)
13
40
1
5
3
5
4
13
24
40
6
10
(
15
40
+
9
40
)
18
40
16
40
23
80
(
3
8
+
1
5
)
(
(3
·
5)
(8
5)
+
(1
·
8)
(5
·
8)
)
11
20
·
120
40
(
1
40
+
40
)
7
40
1
1
40
(15+8)
40
1
4
1
3
22
40
4
12
20
40
4
14
23
40
(
3
80
+
1
80
)
(
1
40
+
40
)
17
40
(
8
+
8
)
7
8
32
40
4
8
1
2
Fig. 5.
An output example with edges drawn as Bezier curves (scaled down)
We i ghtTransfer.
Suppose we delete a vertex
v
such that the edges (
u
,
v
) and (
v
,
w
)
for vertices
u
and
w
exist. If both edges are heavy, it is possible that many students
reached
w
from
u
with
v
as an intermediate step. Hence, after the removal, an edge
(
u
,
w
) becomes more valuable to us because this edge can also partially represent the
steps described above. We can model this by creating edge (
u
,
w
)—if it did not exist—
and increasing its weight by min
for the remainder of the algorithm.
Similar weight transfers make sense also in more complicated situations.
{
w
(
u
,
v
)
,
w
(
v
,
w
)
}
3.3
Experiments and Evaluation
Also the algorithm for calculation graphs was implemented in Java. We used real-world
data generated in user studies, with graphs of 107 and more vertices. The largest graph
had 1031 vertices and 1549 edges. As for general graphs, we mainly used the A4 paper
size as the prescribed drawing area. The tests were performed on a 3 GHz CPU with 4
GB RAM. Figure 5 shows an outputexampleusing Bezier curves, which, in our opinion,
is the nicer and more interesting style compared to the version with orthogonal edges.
Full examples can be found in the extended version [2]. Our main results are as follows.
-
A preprocessing that removes the lightest vertices often improves the output, i.e.,
the drawn subgraph is heavier; see Table 4 in the extended version [2].
-
There was no significant influence of the chosen layering algorithm on the weight of
the final subgraph, especially when using the postprocessing for vertex reinsertion.
-
Tak ing the weight of crossing edges into account in the adjacent exchangeheuristic
for crossing minimization reduces the weight of crossing edges significantly (factor
>
2) and causes only few additional crossings; see Table 5 (extended version [2]).
-
The computation for the largest graph with 1031 vertices took 3 to 4 seconds, de-
pending on the parameters; most of the time was spent on the adjustment of seg-
ments in the edgerouting step and on writing the outputfile(about 2 seconds).
