Information Technology Reference
In-Depth Information
Theorem 1.
The recognition of graphs with USqPCR or UCuPCR is NP-complete.
v
3
v
2
v
v
4
v
1
v
5
v
6
.
(a)
(b)
(c)
Fig. 2. (a)
Aligninggraph
(b)
Box graph
(c)
USqPCR of box graph
Due to the similarity, we only want to provide the strategy of the proof. The logic
engine of the proof by Bremner et al. [3] is composed of copies of the boxgraph, see
fig. 2. Since in any USqPCR of the boxgraph the rectangular shape of the USqPCR
remains, see fig. 2, the recognition of a USqPCR of the composed graph is equivalent
to the recognition of a non-overlapping layout of the corresponding logic engine.
3
The Strategy
Let
G
=(
V,E
) be a subgraph of some grid
=(
V
G
,E
G
).InordertofindaUPCR of
G
,weset
V
:=
V
G
, since independent vertices can easily be removed from a CR. The
idea of the method is to start with a UPCR
ˆ
:
V
G
n
) of
, and then to modify
ˆ
by removingunwanted contacts one by one, that are contacts corresponding to edges
in
E
:=
E
G
\
ₒP
(
R
G
E
. We partition the edgeset
E
G
=
i
E
i
and assignto
e
∈
E
i
a direction
n
.For
e
d
i
∈
R
V
are translated by
ʴd
i
. The translation step
ʴ>
0 is chosen small enough, such that
apart from
e
all contacts remain and no additional ones occur. This strategy yields a
straight-forward construction of a final UPCR
ˆ
of
G
:
ˆ
(
v
)=
ˆ
(
v
)+
∈
E
objects corresponding to vertices in a
moving set
M
(
e
)
ↂ
i
|{
e
∈
E
∩
E
i
|
v
∈
M
(
e
)
}| ·
ʴd
i
.
4
Representations with Unit Squares
The square grid
n
) is defined as follows:
S
m,n
:=
v
i,j
i ∈
[
m
]
,j∈
[
n
]
,
v
i,j
,v
i
,j
i−i
S
m,n
=(
V
S
,E
S
) of size (
m
×
j−j
1
=1
.
Theorem 2.
Every subgraph of thesquare grid
S
m,n
has a USqPCR.
Proof.
We consider subgraphs of type
G
=(
V
S
,E
);forsubgraphs with
V
V
S
,
the theorem follows by removing independent vertices. The proof applies the strategy
described in Section 3. We fix an
ʵ
ↂ
(0
,
1) and present a USqPCR
ˆ
of
∈
S
m,n
, see also
Figure 3:
ˆ
:
V
2
)
ₒP
R
(
ˆ
(
v
i,j
)=
S
(
i
−
jʵ,j
+
iʵ
)
.
