Information Technology Reference
In-Depth Information
(a)
(b)
(c)
Fig. 1.
(a) An embedded and clustered (red/blue) pointset. (b-c) Two different ways to construct
contiguous shapes bounding points of the same color.
a unique color, such fragmented maps are difficult to read as human perception of color
changes based on surrounding colors [19] and can be misinterpreted [11].
We want to combine the advantages of existing methods, while attempting to avoid
their problems. That is, we are interested in visualizing embedded and clustered graphs
with non-fragmented and non-overlapping regions. While constructing such represen-
tations is easy in theory, in practice the regions may still have highvisual complexity;
see Fig. 1. Ideally the regions should be as
convex
as possible, as the convex hull best
captures cohesive grouping according to Gestalt theory [12].
With this in mind, we describe MapSets, a method for creating non-fragmented, non-
overlapping regions that are as convex as possible, from a given embedded and clustered
graph. We consider several criteria for measuring convexity of a shape, and propose
a novel geometric problem aiming at optimizing convexity. We present a theoretical
analysis of the problem in Section 3. Next, in Section 4, we describe a practical method
for visualizing clustered graphs. A comparison of the method with existing techniques
is provided in Section 5.
2
Related Work
Set Visualization.
Graph clusters can be viewed as sets over graph vertices. In Venn
diagrams and their generalization, Euler diagrams, closed curves correspond to (possi-
bly overlapping) sets, and overlaps between the curves indicate intersections. Simon-
etto et al. [21] automatically generate Euler-like diagrams, by allowing disconnected
regions, which can be complex and non-convex. Riche and Dwyer [20] propose a way
to avoid the visual complexity problem by drawing simplified rectangular Euler-like
diagrams, that do not depict the intersections between the sets explicitly, by duplicating
objects that belong to multiple sets. In a user study, they found that it is beneficial to
show intersections using simple set regions and strict containment, enabled by the du-
plication. For the setting where the positions of the objects are fixed, Collins et al. [6]
present BubbleSets, a method based on isocontours to overlay such an arrangement
with enclosing set regions. The readability of these visualizations suffer when there are
many overlapping regions. LineSets [2] aim to improve the readability of complex set
intersections and to minimize the overall visual clutter by reducing set regions to simple
curved lines drawn through set elements. KelpDiagrams [7] incorporate classic graph-
drawing “bubble and stick” style graph or tree spanners over the member points in a
