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

Tollis , 1998 ). The effect of this aesthetic on human understanding was demonstrated
in previous user studies ( Purchase , 1998 ; Purchase, Cohen, & James , 1995 ).
In some cases, however, graph layout algorithms cannot avoid producing edge
cluttering due to high edge density or intrinsic connectivity. This is typical of
force-directed layouts that are applied to real world dense graphs: edges connecting
close neighbors in the drawing mix with long range edges impair readability or
even introduce confusion. The situation is even worse when laying out data using
geographical positions. In such cases, the task of identifying flows inside a network
is challenging because displaying a large number of connections with lines results in
visual clutter. Therefore, reducing the clutter in a graph representation is of utmost
importance to the identification of relationships and high-level edge patterns.
Currently, edge bundling techniques are of increasing interest in the graph
visualization community. Put under the spotlight by Holten ( 2006 ), this technique
addresses the issue of reducing edge cluttering in graph drawings by routing edges
into bundles. The resulting graph visualization improves the layout readability by
uncovering high level edge patterns and emphasizing relationships in relational
data. Several rendering techniques have also been proposed in order to improve
this type of visualization. In this section, we will focus on the recent and intu-
itive bundling technique proposed by Lambert, Bourqui, and Auber ( 2010 ). This
bundling algorithm has the advantages of outperforming the execution times of
existing methods and can guarantee that no node-edge overlaps will occur in the
drawing. Furthermore, this work introduces a rendering technique that makes it
possible to perceive bundle density while preserving edge colors.
The remainder of this section is structured as follows: Sect. 6.4.1 reviews related
work on edge bundling methods. In Sect. 6.4.2 , we present the bundling algorithm
of Lambert et al., while Sect. 6.4.3 refers to rendering techniques that can be applied
to enhance edge bundling visualization.

6.4.1 Previous Work

Phan, Ling, Yeh, and Hanrahan ( 2005 ) present a flow map layout technique
based on geometrical node clustering. Edges are routed along the hierarchy tree
branches. This idea has also been used by Holten ( 2006 ) to enhance relationships
in hierarchical (and relational) data. The main drawback of both methods is that the
edges are routed by using a hierarchy tree that can be restrictive in the general case.
Gansner, Koren, and North ( 2005 ) give an improved circular layout algorithm
where the edges are routed on either the outer face or the inner face of the circle.
Edges routed inside the circle are bundled using an edge clustering algorithm that
tries to optimize area utilization. Another edge clustering method is given by Cui,
Zhou, Qu, Wong, and Li ( 2008 ). In this paper, they propose a geometric approach
to create bundles of edges. They build a control mesh based on user interaction or
a Delaunay triangulation. The mesh is then used to compute regions where edges
should be merged. Then, a clustering algorithm based on the orientation of edges is