Information Technology Reference
In-Depth Information
Therefore, we integrated a part of the heuristic of Sander [15]. However, duetothe
height constraint, we usually cannot save too many bends.
EdgeRouting. Finally, only the edges need to be drawn, with several subproblems:
- We have to distribute the ports of the edges at the incident vertices or useasingle
port shared by all edges.
- We indicate the weight of edges by drawing them with different width. Since there
are only few edges that are very heavy, it makes sense to not use a linear dependency
between width and height but, e.g., a logarithmic dependency, or a dependency to
the cube root (which gave the nicest results for ourdrawings).
- We have to distribute the vertical segments of the edges between consecutive layers
such that both overlaps between segments and unnecessary (double) crossingsare
avoided. We first find a relative order of the segments from left to right for each pair
of adjacent layers as follows: For any pair of edges between the layers that do not
have to cross, there is at most one order with an unnecessary crossing.Using these
orders, we build a directed graph of vertical segments. A topological sorting of this
graph yields an order of the segments that avoids all unnecessary crossings.
Once a relative order of the vertical segments is found, we assign the final coordi-
nates. Small improvements are possible that locally optimize the spacing between
the edgesegments and we have put a lot of effort into implementing some of them.
The most valuable optimization was using a force-directed algorithm with repelling
forces between adjacent segments that optimizes the distances between the seg-
ments.
3.2 Extensions
Preprocessing. Similar to ouralgorithm for general graphs, we use a preprocessing step
in which very light vertices and edges are removed in order to speed up the later steps.
Reinsertion of Removed Vertices. After crossing minimization, when the order of ver-
tices is fixed, it is possible that we could safely reinsert some of the removed vertices so
that the available area is used in a better way. We prefer the vertices with the highest im-
portance as defined before and insert them in the leftmost available layer. Note that after
reinserting vertices, we may have to reorder some of layers for crossing minimization.
Bezier Curves. While we try to avoid bends of the orthogonal edges, there still can be
longer edges that have several bends, making them hard to follow. We suggest draw-
ing the edges as smooth curves instead. To this end, we represent each edgesegment
between two adjacent layers as a cubic Bezier curve. As a simple version, this can be
done by making the two bends of the orthogonal edge the two middle control points of
the curve; this yields already quite nice results. We can further improve the drawingsby
adjusting the force-directed algorithm for the vertical segments (i.e., the control points):
First, we can allow horizontal segments to overlap since they are not actual segments
any more. Second, we can add a tendency to putthesegments close to the middle be-
tween the layers in order to avoid sharp bends. We can, however, not place all vertical
segments in the middle; doing so could result in unnecessary crossings of the respective
curves.
 
Search WWH ::




Custom Search