Information Technology Reference
In-Depth Information
MapSets: Visualizing Embedded and Clustered Graphs
Alon Efrat
1
,YifanHu
2
, Stephen G. Kobourov
1
,andSergey Pupyrev
1
,
3
1
Department of Computer Science, University of Arizona, Tucson, Arizona, USA
2
Yahoo Labs, New York, USA
3
Institute of Mathematics and Computer Science, Ural Federal University, Russia
Abstract.
We describe MapSets, a method for visualizing embedded and clus-
tered graphs. The proposed method relies on a theoretically sound geometric
algorithm, which guarantees the contiguity and disjointness of the regions rep-
resenting the clusters, and also optimizes the convexity of the regions. A fully
functional implementation is available online and is used in a comparison with
related earlier methods.
1
Introduction
In many real-world examples of relational datasets, groups of objects (clusters) are an
inherent part of the input. For example, scientists belong to specific research communi-
ties, politicians are affiliated with specific parties, and living organisms are divided into
biological species in the tree of life. Such clusters are often visualized with regions in
the plane that enclose related objects. By explicitly defining the boundary and coloring
the regions, the cluster information becomes evident. In many instances the data objects
are often associated with fixed or relative positions in the plane. In geo-referenced data,
for example, the positions of the objects might be based on their geographic coordi-
nates. Thusanatural problem arises: How to best visualize graphs in which vertices are
divided into clusters and embedded with fixed positions in the plane?
Several existing visualization approaches seem suitable. For example, methods for
visualizing set relations over existing embedded pointsets, such as BubbleSets [6] and
LineSets [2] use colored shapes to connect objects that belong to the same set. Alter-
natively, a geographic map metaphor can be used to represent such data. With self-
organizing maps [22] or geometry-based GMaps [9], objects become cities and cluster
information is captured by uniquely colored countries. While both approaches can pro-
duce compelling visualizations, we argue that neither is perfectly suited to the problem
of visualizing embedded and clustered graphs.
As the number of sets increases, set-based methods generate complex and some-
times ambiguousresults. More recent methods, such as KelpDiagrams [7] and Kelp-
Fusion [15], reduce visual clutter and guarantee unambiguousvisualization. Butmore
importantly, all of these methods result in overlapping regions for the sets, even when the
input sets are disjoint. This unnecessarily increases visual complexity and might mislead
the viewer about the disjointness of the sets. The geographic map approach suffers from
a different problem. A country in the map, that represents a given cluster of vertices,
might not be a contiguousregion in the plane. Even though each cluster is colored with
