Information Technology Reference
In-Depth Information
intersections, we establish a stricter concept of embeddability. In a strong embedding
block regions may only intersect if the corresponding blocks have at least one element
in common, and even more, each intersection face of the contour graph must actually
contain a point, see Fig. 1(b). This is our second well-formedness condition.
Definition 2 (Strong Embeddability).
Asimultaneousembedding
ʓ
of twopartitions
is
strong
if each intersection face of thecorresponding contour graph contains a point
ʓ
(
u
)
for some
u
U
.Twopartitions are
strongly embeddable
if they have a strong
simultaneousembedding.
∈
Obviously, a strong embedding is also weak, since blocks of the same partition have
no common elements, and thus, cannot form intersection faces. The class of strongly
embeddable pairs of partitions is characterized by Theorem 2; we show in Section 3
that deciding the strong embeddability of a pair of partitions is
NP
-complete.
Theorem 2.
Apair of partitionsofa commonuniverse is strongly embeddable if and
only if it has a planarsupport.
Proof.
Let
be a pair of partitions and let
G
ʓ
be the contour graph resulting
from a strong embedding
ʓ
of
{P
0
,
P
1
}
P
1
}
along
G
ʓ
as follows. First recall that the elements of the universe, which correspond to
the nodes in a support, are represented in
ʓ
by points that are drawn inside intersection
faces. Vice versa, since
ʓ
is strong, each intersection face contains at least one point.
Hence, we choose one point in each intersection face as the
center
of this face. We now
create a dummy vertex for each linking face (observe that one block region may induce
several linking faces) and link it to the centers of all adjacent intersection faces. The
resultinggraph is a subgraph of the dual graph of the contour graph
G
ʓ
and therefore
planar. We now connect all remaining vertices in a star-like fashion to the center of
their intersection face, routing the edges in a non-crossing way. We finally remove the
dummy vertices by merging them to an adjacent center, linking all adjacent vertices to
that center. This graph remains planar. It also has the support property, since all inter-
section and linking faces of any block region are connected into a single component,
and with them all vertices of that block region.
Now we construct a strong embedding from a planarly embedded support of
{P
0
,
P
1
}
. We construct a planar support of
{P
0
,
.
To this end, we first construct a tree-based support by deleting edges from cycles as de-
scribed in Section 1.2. Then, we simply inflate the edges of each block-induced subtree.
Since the underlying support is embedded in a planar way, this yields a simple block
region for every block in
{P
0
,
P
1
}
such that two block regions only intersect at the po-
sitions of the nodes. Hence, the constructed block regions together with the nodes of the
support form a strong embedding of
{P
0
,
P
1
}
. We note that the support graph as a planar
graph can in fact be embedded on any point set [18]. Hence, a strongly embeddable pair
of partitions can be strongly embedded on any point set.
{P
0
,
P
1
}
In a strong embedding,asingle block region may still cross other block regions and
intersect the same block regions several times forming distinct intersection faces—as
long as each intersection face contains at least one common point. The last of ourthree
embeddability classes prevents this behavior and requires that the block regions form a
collection of
pseudo-disks
, i.e., the boundaries of every pair of regions intersect at most
