Information Technology Reference
In-Depth Information
Simultaneous Embeddability of Two Partitions
Jan Christoph Athenstadt
1
,TanjaHartmann
2
, and Martin N ollenburg
2
1
Department of Computer and Information Science, University of Konstanz, Germany
2
Institute of Theoretical Informatics, Karlsruhe Institute of Technology(KIT),Germany
Abstract.
We study the simultaneous embeddability of a pair of partitions of
the same underlying set into disjoint blocks. Each element of the set is mapped
to a point in the plane and each block of either of the two partitions is mapped
to a region that contains exactly those points that belong to the elements in the
block and that is bounded by a simple closed curve. We establish three main
classes of simultaneous embeddability (
weak
,
strong
,and
full
embeddability) that
differ by increasingly strict well-formedness conditions on how different block
regions are allowed to intersect. We show that these simultaneous embeddability
classes are closely related to different planarity concepts of hypergraphs. For each
embeddability class we giveafull characterization. We show that (i) every pair of
partitions has a weak simultaneous embedding, (ii) it is
NP
-complete to decide
the existence of a strong simultaneous embedding, and (iii) the existence of a full
simultaneous embedding can be tested in linear time.
1
Introduction
Pairs of partitions of a given set of objects occurnaturally when evaluating two alter-
native clusterings in the field of data analysis and data mining.A
clustering
partitions
a set of objects into
blocks
or
clusters
,such that objects in the same cluster are more
similar (according to some notion of similarity) than objects in different clusters. There
areamultitude of clustering algorithms that use, e.g., an underlyinggraph structure or
an attribute-based distance measure to define similarities. Many algorithms also pro-
vide configurable parameter settings. Consequently, different algorithms return differ-
ent clusteringsandjudging which clustering is the most meaningful with respect to
a certain interpretation of the data must be done by a human expert. For a structural
comparison of two clusterings several numeric measures exist [20], however, a single
numeric value hardly shows where the clusteringsagree or disagree. Hence, a data an-
alyst may want to compare different clusteringsvisually, which motivates the study of
simultaneous embeddability of two partitions.
We p r ov i d e fundamental characterizations and complexity results regarding the si-
multaneous embeddability of a pair of partitions. While simultaneous embeddability
can generally be defined for any number
k
2 of partitions, we focus on the basic case
of embedding
two
partitions, which is also the most relevant one in the data analysis
application. We propose to embed two alternative partitions of the same set
U
into the
plane
≥
2
by mapping each element of
U
to a unique point and each block (of either
of the two partitions) to a region bounded by a simple closed curve. Each block region
must contain all points that belong to elements in that block and no point whose element
belongs to a different block. Hence, in total, each point lies inside two block regions.
R
