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.
Search WWH ::




Custom Search