Information Technology Reference
In-Depth Information
The remaining question is, whether subgraphs of Archimedean grids admit a repre-
sentation with unit squares. In general, this is not the case since we find two forbidden
subgraphs:
K
1
,
5
and the
pufferfishgraph
,whichisa
C
6
together with two private neigh-
bors for all but one vertex, see Figure 6. Table 1 summarizes for which Archimedean
grids, all subgraphs allow for a USqPCR.
Ta b l e 1 .
The table gives an overview for which Archimedean grids each subgraph allows for a
USqPCR. By Corollary 1, each subgraph has a UCuPCR.
square
hexagonal
truncated square
truncated hexagonal
✓
✓
✓
✓
triangular
elongated triangular
snub square
snub hexagonal
✗
✗
✗
✗
rhombi-
trihexagonal
truncated
trihexagonal
trihexagonal
✗
?
?
Lemma 1.
Thepufferfishgraphand
K
1
,
5
have noUSqPCR.
Proof.
We first note that for two touching squares, at least one corner of each square
is involved in the segment of contact; two corners are involved iff the squares have full
side contact. In a USqPCR of
K
1
,
5
,theremust be a corner involved in two contacts
which leads to full side contacts. Since a square has only four sides, it follows that
K
1
,
5
has no USqPCR.
Assume the pufferfish graph has a USqPCR. We first observe that no two squares
have full side contact: Suppose there are two such squares, then one of them represents
avertex
v
of the
C
6
which has 4 independent neighbors. Due to its 4 independent
neighbors, it follows that all of its contacts are full side contacts. It is easy to see that
repeating the argument for a neighbor of
v
with degree 4 leads to a contradiction. Hence,
no two squares have full side contact and each corner of the squares in the
C
6
is involved
in a contact segment.