Information Technology Reference
In-Depth Information
that if (
u,v
)
∈
E
,then
r
i
(
u
)
<r
i
(
v
) since
u/
∈
M
((
u,v
)) and
v
∈
M
((
u,v
)).
Consequently,
ˆ
(
u
) and
ˆ
(
v
) have proper contact iff (
u,v
)
∈
E
.
2
)
: Theparameters
r
i
(
v
)
can
Remark 1.
Theconstructionhasrunning timeof
O
(
|
V
|
be determined in
O
(
n
|
V
|
)
andtheconstruction can be produced in
O
(
|
V
|
)
. Since
n
≤
2
)
.
|
V
|
,this gives an overall running timeof
O
(
|
V
|
Remark 2.
Choosing specific values for
ʵ
and
ʴ
,further properties can be guaranteed:
Wi th
ʵ
=
2
and
ʴ
=
1
2
n
+2
one obtains a USqPCR
ˆ
of
G
where the proper contacts
and non-contacts are guaranteed to be of size
ʴ
.As
ʵ
and
ʴ
approach
0
,theconstact
sizes are arbitrarily close to
1
.This is exploited inSection 6forUSqPCR with
4
k
-gons.
5
Representations with Unit Cubes
In this section we investigate further subgraphs of grids for UPCR with cubes.
5.1
d
-Dimensional Grid
Indeed, Theorem 2 can be generalized to all dimensions. As a generalization of the
square grid, we define the
d
-dimensional grid
n
=(
V
S
,E
S
):
S
n
:=
v
x
x
1
=1
[
n
]
d
,
(
v
x
,v
y
)
d
S
∈
x
−
y
(a)
(b)
(c)
2
; for the thick edges, the moving sets are indicated by the framed vertices
Fig. 4. (a)
Cubic grid
S
(b)
UCuPCR
ˆ
of
S
2
(c)
Illustration of modification step.
n
admits a UPCR with
d
-cubes.
Theorem 3.
Every subgraph of the grid
S
Proof.
The proof applies the strategy presented in Section 3. First, we give a UPCR
with
d
-cubes of
n
, depicted in Figure 4. We choose
ʵ
(0
,
1),
ʴ<
n
min
S
∈
{
ʵ,
1
−
ʵ
}
d×d
:
and define the UPCR with the help of matrix
A
∈
R
⊛
⊝
⊞
⊠
1
ʵ ...ʵ
−
.
ˆ
:
V
.
.
.
d
)
ₒP
(
R
ʵ
1
A
:=
.
.
.
.
.
.
.
ʵ
ˆ
(
v
x
)=
Q
(
A
·
x
)
−
ʵ...
−
ʵ
1
In order to prove that
ˆ
is a UPCR of
n
with
d
-cubes, we note: Two axis-aligned unit
d
-cubes with characteristic corners
x
and
y
, have proper (
d
S
−
1)-dimensional contact
