Information Technology Reference
In-Depth Information
any cycles. For any support
G
p
of a pair of partitions
{P
0
,
P
1
}
we can always create
a tree-based support
G
p
by removing edges from cycles: Suppose there exists a block
B
∈P
0
such that
G
p
[
B
] contains a cycle
K
. If the vertices in
K
are also contained in
a common block of
P
1
, we can just remove a random edge from
K
without destroying
the support property. Otherwise, we can remove an edge from
K
that connects vertices
in two different blocks of
P
1
without destroying the support property.
The
bipartite map
G
b
(
H
) of a hypergraph
H
=(
V,
S
) is defined as the bipartite
graph
G
b
(
H
)=(
V
∪S
,E
b
) that has a node for each vertex in
V
and for each hyperedge
in
S
[21]. A node
v
∈
V
is adjacent to a node
S
∈S
if
v
∈
S
. We say that
G
b
(
H
) is
the bipartite map of a pair of partitions
{P
0
,
P
1
}
if
H
=
H
(
P
0
,
P
1
).
Finally, we define the
block intersectiongraph
G
s
(
P
0
,
P
1
) as the graph with vertex
B,B
}|
B
set
V
s
=
.Thus
G
s
has a vertex for
each block and an edge between any two blocks that share a common element. Since
only blocks of different partitions can intersect, we know that
G
s
is bipartite.
P
0
∪P
1
and edgeset
E
s
=
{{
B
∩
=
∅}
2
The Main Classes of Embeddability
We define three main concepts of simultaneous embeddability for pairs of partitions.
We will see that these concepts induce a hierarchy of embeddability classes of pairs of
partitions. We begin with
weak embeddability
, which is the most general concept.
Definition 1 (Weak Embeddability).
Asimultaneousembedding of twopartitionsis
weak
if notwoblock regionsofthesamepartition intersect. Twopartitions are
weakly
embeddable
if they have aweak simultaneousembedding.
Prohibiting intersections of block regions of the same partition is our first well-formed-
ness condition. A weak embedding emphasizes the fact that the blocks in each partition
are disjoint. Since the blocks of any partition are disjoint by definition, it is not surpris-
ing that any pair of partitions is weakly embeddable (see Fig. 1(a) for an example).
Theorem 1.
Any twopartitionsofa commonuniverse are weakly embeddable on any
pointset.
Proof.
A spanning forest (in fact, any planar graph) on
n
nodes can always be drawn in
a planar way on any fixed set of
n
points in the plane [18]. Let now
be a partition. We
choose arbitrary, but distinct points in the plane for the elements of
U
.Wethengenerate
a spanning tree on the elements in each block and embed the resulting forest in a planar
way on the points. Slightly inflating the thickness of the edges of the trees yields simple
bounded block regions. We can do this independently for a second partition on the same
points and obtain a weak simultaneous embedding.
P
Although the concept of weak embedding does not seem to provide interesting in-
sights into the structure of a given pair of partitions, it guarantees at least the existence
of a simultaneous embedding for any pair of partitions that is more meaningfulthan
an arbitrary embedding.Anobvious drawback of weak embeddings is that the block
regions of disjoint blocks are allowed to intersect, as long as both blocks belong to
different partitions—even if they do not share common elements. Following the gen-
eral idea of Euler diagrams [8], which do not show regions corresponding to empty
