Information Technology Reference
In-Depth Information
Consequently, the inner face bounded by the squares of the
C
6
is an orthogonal 8-
gon (of T- or Z-shape) with side lengths
≤
1. This implies that private neighbors cannot
be placed in the inner face and the two convex corners belonging to different squares
do not account for a contact: a contradiction.
Corollary 2.
Not all subgraphsofthetriangular, e l ongated triangular, s nubsquare,
snub hexagonal, andrhombitrihexagonal grid have a USqPCR.
Proof.
K
1
,
5
(and the pufferfish graph) are induced subgraphs of the triangular, elon-
gated triangular, snubsquare, and snubhexagonal grid. The pufferfish graph is an in-
duced subgraph of rhombitrihexagonal grid.
6
Representations with Regular Polygons
In this section, we consider UPCR with further regular polygons and for ease, refer to
them as polygons. To do so, we introduce the notion of
pseudo polygons
.A
pseudo
n
-
gon
(with side length
s
)isasubset of a regular
n
-gon, which includes a central segment
(of length
s
) of each boundary edge. A segment of a boundary edge is called
central
if
their midpoints coincide. It can be understood as a
n
-gon with cut-off corners, consider
Figure 7.
≥
Fig. 7.
Examples of pseudo-triangles and pseudo-squares
Lemma 1.
Let
G
be agraphwithaUPCR
ˆ
with regular
k
-gons and
cs
(
ˆ
)
>
1
−
s
.
Then,
G
has a UPCR with pseudo
k
-gons with side lengthatleast
s
.
Proof.
This UPCR is obtained from
ˆ
by inscribing apseudo
k
-gon into each
k
-gon:
Consider two touching
k
-gons and the sides realizing the proper contact. The midpoints
of these sides differ by
<s
since cs(
ˆ
)
>
1
s
. Hence, every contact can be certified by
two intersecting central segments of size
s
. Since the pseudo
k
-gons (with side length
s
) contain these segments, the contacts remain. Additionally, no new contacts occur,
because each pseudo
k
-gon is a subsets of a
k
-gon. Hence,
ˆ
still serves as a UPCR.
−
6.1
Representations with Regular
4
k
-gons
Corollary 3.
Every subgraph of thesquare grid
S
m,n
has a UPCR with regular
4
k
-
gons,
k
≥
1
.
Proof.
Note that 4
k
-gons are pseudo-squares with side length
s
k
:= sin(
4
k
). Choosing
ʵ<
s
2
in the proof of Theorem 2, we obtain a UPCR
ˆ
for every subgraph
G
of
S
m,n
with
cs
(
ˆ
)
>
1
−
s
k
. With this, the claim follows directly from Theorem 2 and
Lemma 1.
