Information Technology Reference
In-Depth Information
(a) Removing a linking face
(b) Removing a background face
Fig. 2.
Two cases for transforming astrong embedding into a proper strong embedding
al. [5] who showed that deciding the existence of a planar support and a 2-outerplanar
support in general hypergraphs is
NP
-hard. However, we consider a restricted subclass
NP
of 2-regular hypergraphs, thus, the
-hardness of our problem does not directly follow
from the previousresults. Moreover, other special cases, e.g., finding path, cycle, tree,
and cactussupports are known to be solvable in polynomial time [3, 5, 14]. Together
with the characterization of Theorem 2, Theorem 4 immediately implies that testing the
vertex planarity of a 2-regular hypergraph is
NP
-complete.
Theorem 4.
Deciding thestrong embeddability of a pair of partitionsis
NP
-complete.
The existing hardness results [5, 14] rely on elements that are contained in more than
two hyperedges and could not be adapted to our 2-regular setting. Instead we prove the
hardness of deciding strong embeddability by a quite different reduction from the
-
complete problem
MONOTONE PLANAR
3S
AT
[10]. A monotone planar 3Sat formula
˕
is a 3Sat formula whose clauses either contain only positive or only negated literals (we
call these clauses
positive
and
negative
) and whose variable-clause graph
H
˕
is planar.
A
monotone rectilinearrepresentation
(MRR) of
˕
is a drawing of
H
˕
such that the
variables correspond to axis-aligned rectangles on the x-axis and clauses correspond to
non-crossing E-shaped “combs” above the x-axis if they contain only positive variables
and below the x-axis otherwise; see Fig.4(a).
An instance of
MONOTONE PLANAR
3S
AT
is an MRR of a monotone planar 3Sat
formula
˕
. In the proof of Theorem 4 we will construct a pair of partitions
NP
{P
0
,P
1
}
˕
that admits a strong embedding if and only if
˕
is satisfiable.
For the sake of simplicity, we restrict the class of strong embeddingstothesub-
class of
proper strong embeddings
, which is equivalent, as we can argue that a pair
of partitions has a strong embedding if and only if it also has a proper one. A strong
embedding is
proper
if the contour graph does not contain background or linking faces
that are adjacent to only two other faces. Figure 2 illustrates how background or linking
faces violating this condition can be removed, transforming astrong embedding into
a proper one. We say that two proper strong embeddingsare
equivalent
if the embed-
dings of their contour graphs are equivalent, i.e. if the cyclic order of the edges around
each vertex is the same. A pair of partitions has a
uniquestrong embedding
if all proper
strong embeddingsareequivalent. Note that, analogously to the definition of equiva-
lence of planar graph embeddings, two equivalent proper strong embeddingsmayhave
different unbounded outer background faces. Our construction in the hardness proof is
independent of the choice of the outer face.
Next we define a special pair of partitions that has a unique grid-shaped embedding
as a scaffold for the gadgets in the subsequent proof of Theorem 4. The first step is
