Automatic Drawing of Links in Graphs and Networks
Connecting dots with straight lines is trivial. What about avoiding intersections?
The automatic drawing of links of graph and network structures is also known as edge routing. Edge routing algorithms calculate suitable routes for the links (i.e., edges) of a graph while keeping the locations of the nodes fixed. There are several possible routing styles like the orthogonal, polyline, or organic style. Most algorithms try to omit node-edge overlaps when calculating the specific routes.
There are several use cases where the application of such algorithms is beneficial, e.g., for the visualization of geospatial data where the nodes are already placed in the drawing or for incremental layouts where new edges are added to an existing graph layout. For such scenarios, edge routing provides an easy and fast way to gain insight into the relationships among the elements.
yFiles is a commercial programming library designed explicitly for diagram visualization. The advanced layout algorithms of yFiles can comfortably transform the data in a readable, pleasing, and informative network. yFiles offers edge routing algorithms for several different edge styles. Namely, it supports orthogonal edge paths that consist only of horizontal and vertical segments (see Fig. Orthogonal Style), polyline edge paths that have non-orthogonal segments (see Fig. Polyline Style), and organic edge paths that consist of smooth curves routed around the nodes (see Fig. Organic Style). Also, it supports routing of bus-like structures in which edge segments are bundled to buses, i.e., segments shared by multiple edges to which shorter segments that connect to actual nodes are attached (see Fig. Bus Style).
The Polyline Edge Routing algorithm of yFiles provides a sophisticated implementation that routes edges either in an orthogonal, polyline, or bus-like style and tries to produce routes with a low number of crossings and bends. Also, it supports many advanced features like the placement of labels, the grouping of edges, and the specification of intermediate points that should be part of the calculated route. Furthermore, the user can specify the location to which the edges should connect to the source or target nodes and can even determine whether the paths should be monotone between the source and the target node. Besides routing all edges, the user can also specify a subset of edges that should be routed while the remaining edges stay fixed.
The outstanding number of supported features and constraints make this algorithm applicable to various scenarios. The following interactive applications showcase some of them:
The Channel Edge Routing of yFiles is a high-speed routing algorithm that yields orthogonal edge routes. Compared to the algorithm above, it supports fewer features and may produce node-edge overlaps. Nevertheless, it may be the right choice for larger graphs and interactive usage when the runtime is especially crucial.