Information Technology Reference
In-Depth Information
T
m,n
has a UCuPCR.
Theorem 4.
Every subgraph of thetriangular grid
Proof.
The proof uses the observation that subgraphs of
T
1
,n
allow for USqPCR. There-
fore, contacts corresponding to level edges are realized alternating in planes parallel to
the
xy
and
xz
plane. Choosing
ʵ
1
∈
(0
,
1) and
ʴ<
n
+1
min
{
ʵ,
1
−
ʵ
}
,wedefinea
UCuPCR of
T
m,n
, see also Figure 5:
ˆ
:
V
3
)
ˆ
(
v
)=
Q
i,
ₒP
(
R
j
j
(1 +
ʵ
)
,
if
v
=
b
i,j
,
Q
i
+
ʵ, j
(1 +
ʵ
)+
ʵ, j
+1
if
v
=
t
i,j
.
It is easy to verify that
ˆ
is a UCuPCR of
T
m,n
with contact size
cs
(
ˆ
)
≥
(1
−
ʵ
).
Additionally, it holds that
sp
(
ˆ
(
u
)
, ˆ
(
v
)
,d
i
)
≥
ʵ
for the following direction vectors:
For an edge
e
∈
E
i
we set the direction vector
d
i
to
d
1
:= (1
,
0
,
0),
d
2
:= (0
,
0
,
1),
d
3
:= (0
,
0
,
1
,
0). The moving set belonging to an edge
is slightly more involved. For a level edge
e
,
M
(
e
) roughly consists of the vertices in the
level with larger index; for a line edge, it consists of the line vertices with larger index:
for
e
=(
b
i,j
,t
k,l
)
−
1),
d
4
:= (0
,
1
,
0),
d
5
:= (0
,
−
∈
E
2
∪
E
4
,wedefine
M
(
e
):=
{
b
i,r
|
r>j
}∪{
t
k,r
|
r
≥
l
}
,and
for
e
=(
b
i,j
,t
k,l
)
∈
E
3
∪
E
5
,wedefine
M
(
e
):=
{
b
i,r
|
r
≥
j
}∪{
t
k,r
|
r>l
}
,and
for
e
=(
x
i,j
,x
i,j
+1
)
∈
E
1
,wedefine
M
(
e
):=
{
x
i,r
|
r>j
}
.Figure 5 depicts the
moving sets, direction vectors and modifications.
As the proof is analogous to the proof of Theorem 2, we give some useful observa-
tions and leave the rest to the reader: The translation vector
d
(
e
) of an edge
e
is parallel
to each of the crucial cube facets, realizing contacts corresponding to edges of type
(
u,v
)
∈
E
\{
e
}
with
u
∈
M
(
e
) and
v/
∈
M
(
e
). Also note that
r
i
(
v
)
≤
n
+1and hence
sp(
ˆ
(
u
)
, ˆ
(
v
)
,d
i
) for all (
u,v
)
/
r
i
(
u
)
·
ʴ
≤
(
n
+1)
ʴ
≤
ʵ
≤
∈
E
S
and all
d
i
. Combining
this, the construction yields a UCuPCR for each subgraph of
T
m,n
.
5.3
Archimedean Grids
There exist eleven grids originating from regular and semi-regular tilings of the plane,
so called
Archimedean grids
, which are depicted in Table 1. As mentioned before,
UCuPCR for subgraphs of five Archimedean grids are known [1, 2]. With the results of
the previous section, UCuPCR for subgraphs of all Archimedean grids follow directly:
Corollary 1.
Every subgraph of an Archimedean grid has a UCuPCR.
Proof.
Observe that Archimedean grids are subgraphs of the triangular grid. For prov-
ing this fact, we provide convincing pictures in Table 1. With this observation, the claim
follows directly from Theorem 4.
Fig. 6.
The pufferfish graph and the star
K
1
,
5
