Information Technology Reference
In-Depth Information
area. We first remove vertices from each layer, so that the height of the layer is small
enough. Afterwards, we remove whole layers until the width requirement is fulfilled.
We first remove single vertices because this step can significantly influence the total
weight of layers and, therefore, the choice of layers that will be deleted. The removal
from the layers is done from left to right since the removal of a vertex from a layer can
cause other vertices right of it to also be removed, if they become unreachable from
s
.
When removing from a layer, we should prefer light vertices. However, we must
also take the heights of vertices into account: Removing ahigh vertex may save as
much space as removing several lighter vertices whose weight sums uptoalarger value.
Hence, we measure the importance of a vertex
v
as
i
(
v
)=
w
(
v
)
/
h
v
and remove as many
vertices of lowest importance as necessary so that the layer fits into the drawing area.
We also tried other importance measures by taking the possible decrease of the width
of the layer or the decrease of its area into account when removing a vertex. However,
these measures did not perform better than the simpler height-based measure.
Once all layers have a feasible height, we will remove complete layers so that we are
within the allowed total width. Note that we must always keep gaps between adjacent
layers so that the edges can be drawn. The removal of layers is also done from left
to right. We do this based on the importance of a layer
L
, which we define as
i
(
L
)=
∑
L
w
(
v
)
/
width(
L
), where the width of
L
is determined by its widest vertex.
v
∈
Crossing Minimization.
For the crossing minimization, we use the methods commonly
used in the Sugiyama framework, which are based on considering only (parts of) edges
between adjacent layers, butdosomultiple times. For the adjacent exchangeheuristic,
we also considered the version where the weight of crossing edges is minimized. This
heuristic just performs swaps of adjacent vertices in a layer—if this reduces the number
(or weight) of crossings. Hence, weights can easily be integrated.
EdgeRemoval.
Even after crossing minimization, there could still be too many cross-
ingsforthedrawing to be well readable, if the graph is dense. Hence, we add a step
in which edges are removed, if necessary. To this end, we introduce a measure for the
importance of an edge
e
:If
E
(
e
) is the set of edges that cross
e
, then the importance
of
e
is
i
(
e
)=
w
(
e
)
/
(
E
(
e
)
w
(
e
)).Theresult is that edges without a crossing are con-
sidered most important and will never be removed. Furthermore, an edge that crosses
heavy edges—which are more valuable to us—will more likely be removed.
∑
e
∈
Gaps in Layers.
Now, we know the orders of vertices in layers, where a layer also
contains edges that are routed through several layers. We improve readability by using
different gaps between the objects in a layer: Two edges are drawn closer together than
two vertices, and edges that stay parallel until the next layer can be drawn even closer.
While the different gaps make the drawings nicer, the consequence is also that only
now we know the precise height each a layer. In some cases, this can make it necessary
to remove another vertex of a layer, which, again, is done based on the importance
measure.
Coordinate Assignment.
For the final adjustment of the vertex positions, we still have
some flexibility if the vertices (and edges) in the layer do not consume the total avail-
able height. We can use this flexibility and try to minimize the number of edge bends.
