Information Technology Reference
In-Depth Information
set. KelpFusion [15] adds filled-in regions to provide a stronger sense of grouping for
close elements. A significant limitation of all these set visualization techniques is that
they produce overlapping regions even when the sets are disjoint.
Visualizing Graphs as Maps.
The geographic map metaphor is utilized as visual in-
terface for relational data, where objects, relations between objects, and clustering are
captured by cities, roads, and countries. Using maps to visualize non-cartographic data
has been considered in the context of spatialization [22]. Maps of science showing
groups of scientific disciplines are used by a wide range of professionals to grasp de-
velopments in science and technology[4].
The geographic map metaphor is used in the Graph-to-Map approach (GMap) [9].
GMap combines graph layoutandgraph clustering,together with appropriate coloring
of the clusters and creating boundaries based on clusters and connectivity in the original
graph. However, since layoutandclustering are two separate steps, a region represent-
ing acluster may often be fragmented; see Fig.7(b).Such fragmentation makes it dif-
ficult to identify the correct regions and can result in misinterpretation of the map [11].
Note that in the setting when either an input embedding or clustering can be modified,
the GMap approach can be improved to achieve contiguousregions [13].
Colored Spanning Trees.
From an algorithmic perspective, our geometric approach
of optimizing convexity of regions that cover points in the plane is related to several
problems in which the inputisamulticolored point set [1, 3]. The group Steiner tree
problem deals with a graph with colored vertices, and the objective is to find a minimum
weight subtree covering all colors [16]. Also related is the problem of computing span-
ninggraphs for multicolored point set [10]. The problem is motivated by optimizing the
amount of “ink” needed to connect monochromatic points that arise when visualizing
sets using the KelpFusion technique. These trees cannot be directly used as “skeletons”
of regions in the plane as they can result in overlapping regions.
3
Constructing Contiguous Non-overlapping Regions
We a s sume that the input instance consists of a set of objects
P
with fixed positions
p
i
∈
R
2
for all
i
P
, for example, cities and their geographic locations. In practical
applications labels are often associated with the objects. In this case, we assume that
non-overlapping bounding boxes for the labels are given. The input also specifies a
clustering
C
=
∈
k
{
C
1
,...,C
k
}
of the objects with
∪
i
=1
C
i
=
P
and
C
i
∩
C
j
=
∅
for
i
=
j
. We wish to enclose all objects of the same cluster by a single contiguousregion
so that regions corresponding to different clusters do not overlap.
On one hand, simply overlaying each cluster with a convex region (e.g., bounding
box or convex hull) is not always a valid solution, as it might cover elements in other
clusters. On the other hand, representing clusters by some minimal regions (e.g., span-
ning or Steiner trees) is also not always valid, as it might result in intersecting regions.
We r e quire regions that are contiguous and disjoint, and it is not difficult to see that
such regions can be easily computed. We can begin by computing a crossing-free span-
ning tree of points belonging to some cluster. Once the tree is constructed, its vertices
and edges become “obstacles” that should be avoided by subsequent trees. Note that
