Graph Visualization For Geography - Methods for Multilevel Analysis and Visualisation of Geographical Networks - page 91

used to merge the edges. A post processing step is applied to reduce the effect of
“zigzag” edges.
Recently, Holten & Wijk ( 2009 ) introduced a force-directed heuristic to bundle
edges and, therefore, to unclutter a representation of a graph where the node
positions are fixed. In this heuristic, dummy nodes are inserted in order to split edges
into segments. A similarity measure between edges is computed to determine which
of the dummy nodes should interact. Dummy nodes of any two interacting edges are
linked by inserting dummy edges. Bundles are obtained by running a force-directed
algorithm while preserving the positions of the original nodes.

6.4.2 Edge Bundling Method of Lambert et al.

This technique uses edge routing to bundle edges. A grid is computed according
to the node positions. This grid is then used to compute the shortest routes for
each edge. In the same way that highways attract more drivers than smaller roads,
frequently taken paths are used to bundle edges.

Grid Computation

To compute the shortest paths for each original edge, a grid graph is created on
which the nodes of the original graph are connected. This grid is computed by
discretizing the plane into cells using original node positions.
To obtain a multi-resolution grid graph, one can use a quad tree where the plane
is decomposed in four parts until it contains at most one element. Such an approach
is efficient in terms of computation time because its complexity is O .

On one hand, it generates a large grid, and on the other hand, large cells promote
horizontal and vertical paths. Voronoi diagrams can also be used to generate the
grid graph. In a Voronoi diagram, the cells are regions of the plane in which points
of a cell are closer to the cell's site (here, the original nodes) than to any other
site. Using classical Voronoi diagram does not guarantee that node edge overlaps
will be prevented in the case of non-point size nodes. However, that problem can
be easily addressed by using a constrained Voronoi diagram that takes into account
the node size. This method generates a small grid graph that can be computed in
O

( | V |· log ( | V | ))

, but it generates large cells for a sparse region. Due to the routing
method used in the next step of the algorithm, these large cells will create large
detours. Lambert et al. propose a hybrid algorithm based on both quad trees and
Voronoi diagrams. In this algorithm, the quad tree cell sizes are parameterized to
generate different levels of clutter reduction. Then, Voronoi diagrams are used to
construct the final grid graph. Figure 6.8 b shows the grid graph obtained with this
hybrid approach. Because the quad tree adds O

( | V |· log ( | V | ))

time
complexity is preserved. Therefore, the resulting grid graph is of reasonable size.

( | V | ) nodes, the O ( | V |· log ( | V | ))