Information Technology Reference
In-Depth Information
If the embedding is not canonical we show that it can be transformed into a canonical
embedding as follows. In a non-canonical embedding it is possible that two blocks
B
i
and
B
j
intersect in a variable cell
x
k
and have a shared element in their intersection face
in the cell of
x
k
rather than in the home cell of that element. This means, on the other
hand, that in some shared home cell
ʳ
of
B
i
and
B
j
, say in the upper half, at least one of
the two blocks is opened (as there is no more shared element to put into an intersection
face). Thusthegrid cell
ʳ
splits the E-shaped block region of one or both blocks in the
upper half into two disconnected components, meaning that each opened block crosses
at least two variable cells in order to connect both components via the lower half. Hence
we can safely split any block that is opened in
ʳ
in the cell of variable
x
k
, re-connect it
inside
ʳ
, and place the shared element of
B
i
and
B
j
into its home cell
ʳ
. This removes
the block intersection in the cell of
x
k
. Once all block crossings within variable cells
are removed, the resulting embedding is a canonical embedding and we can derive the
corresponding satisfying variable assignment.
4
Extensions and Conclusion
We have characterized three main embeddability classes for pairs of partitions, which in
fact form a strict hierarchy (see full version [1]), and we have shown
NP
-completeness
of deciding strong embeddability. From a practical point of view the class of strong
embeddings is of particular interest: it guarantees that every intersection between block
regions is meaningful as it contains at least one element, but, in contrast to full embed-
dings, it allows multiple disconnected intersection regions between the same two blocks
and it allows two blocks to cross.
There are interesting subclasses of strong embeddingsthatfurther structure the space
between strong and full embeddability. They are discussedinmoredetailinthefull
version [1]. In
single-intersection strong embeddings
we adapt the
uniqueintersection
region
condition of full embeddings, but still permit that two blocks cross in the em-
bedding. This new class is a truesubclass of strong embeddings. It is open whether
the corresponding decision problem is still
-complete since the proof of Theorem 4
is based on the existence of multiple intersection regions between pairs of blocks. In
strong grid embeddings
,atruesubclass of single-intersection strong embeddings, the
blocks of
NP
P
1
are embedded as horizontal and vertical ribbons, respectively,
which intersect in a matrix-like fashion.
It is an interesting direction for future work to generalize our embeddability concepts
to
k>
2 partitions. While weak embeddability and its properties extend readily to any
number of partitions, it is less obvioushowtogeneralize strong and full embeddability.
One possibility is to require the properties in a pairwise sense; otherwise constraints
for new types of faces in the contour graph belonging to more than one butlessthan
k
block regions might be necessary. On the practical side, future work could be the
designofalgorithms that find visually appealing simultaneous embeddingsoftwoor
more partitions. Finally, if the partitions are clusteringsonagraph, one would ideally
want to simultaneously draw both the partitions and the underlyinggraphs.
P
0
and
Acknowledgments.
We thank the anonymous reviewers for helpful comments.
