Information Technology Reference
In-Depth Information
Asimultaneous embedding of two partitions shares certain properties with set visu-
alizations like EulerorVenndiagrams [8,12,19]. Its readability will be affected by well-
formedness conditions for the intersections of the different block regions. Accordingly,
we define a (strict) hierarchy of embeddability classes based on increasingly tight well-
formedness conditions: weak , strong ,and full embeddability. We show that (i) any two
partitions are weakly embeddable, (ii) the decision problem for strong embeddability
is
-complete, and (iii) there is a linear-time decision algorithm for full embeddabil-
ity. We fully characterize the embeddability classes in terms of the existence of a planar
support (strong embeddability) or in terms of the planarity of the bipartite map (full em-
beddability). Interestingly, both concepts are closely related to hypergraph embeddings
and different notions of hypergraph planarity. Our
NP
-completeness result implies that
vertex-planarity testing of 2-regular hypergraphs is also
NP
NP
-complete.
1.1
Related Work
In information visualization there are a large variety of techniques for visualizing clus-
ters of objects, some of which simply map objects to (colored) points so that spatial
proximity indicates object similarity [6, 16], others explicitly visualize clusters or gen-
eral sets as regions in the plane [9, 19]. These approaches are visually similar to Euler
diagrams [8, 12], however, they do not give hard guarantees on the final set layout, e.g.,
in terms of intersection regions or connectedness of regions, nor do they specifically
consider the simultaneous embedding of two or more clusterings or partitions.
Clustered planarity is a concept in graph drawing that combines a planar graph lay-
out with a drawing of the clusters of a single hierarchical clustering.Clusters are repre-
sented as regions bounded by simple closed and pairwise crossing-free curves. Such a
layout is called c-planar if no edge crosses a region boundary more than once [11].
The simultaneous embedding of two planar graphs on the same vertex set is a topic
that is well studied in the graph drawing literature, see the recent survey of Blasiuset
al.[2].Inasimultaneous graph embedding each vertex is located at a unique position
and edges contained in both graphs are represented by the same curve for both graphs.
The remaining (non-shared) edges are embedded so that each graph layout by itself is
crossing-free, butedges from the first graph may cross edges in the second graph.
Some of ourresults and concepts in this paper can be seen as a generalization of
simultaneous graph embedding to simultaneous hypergraph embedding if we consider
blocks as hyperedges: all vertices are mapped to unique points in the plane and two hy-
peredges, represented as regions bounded by simple closed curves, may only intersect if
they belong to different hypergraphs or if they share common vertices. Several concepts
for visualizing asingle hypergraph are known [4, 5, 14, 15, 17], but to the best of our
knowledgethesimultaneouslayout of two or more hypergraphs has not been studied.
1.2
Preliminaries
Let U =
{
u 1 ,...,u m }
be a finite universe. A partition
P
=
{
B 1 ,...,B n }
of U groups
the elements of U into disjoint blocks ,i.e.,everyelement u
U is contained in exactly
one block B i ∈P
. In this paper, we consider pairs
{P 0 ,
P 1 }
of partitions of the same
Search WWH ::




Custom Search