2
$\begingroup$

Let $\cal T$ be a monohedral, edge-to-edge tiling of the plane, with prototile $T$ a simple polygon, and with one edge $e^*$ of $T$ distinguished. Associate a graph $G=G_{\cal T}$ with $\cal T$ as follows. Each copy $T_i$ of $T$ in $\cal T$ is a node of $G$, and $T_1$ and $T_2$ are connected by an arc in $G$ if they share a distinguished edge of either tile.

$G$ is a planar graph without isolated nodes, often disconnected, and without loops as @DimaPasechnik observed. Note that $G$ depends on both $T$ and $e^*$:

          PentagonTiling
          Distinguished edges marked red.
          Top: $G =$ collection of $4$-cycles. Bottom: $G =$ collection of segments.
My question is: Which graphs $G_{\cal T}$ can be realized by some tiling $\cal T$. Because there seems to be considerable freedom to "design" $G$ when $T$ is a regular $\{3,4,6\}$-gon, or tiles with several equal-length edges (such as polyominoes1), perhaps this is an easier question:

Q. What are some graphs $G$ that cannot be realized by some tiling $\cal T$?

Added. An example where choosing the "base" of the horn-shape as the distinguished edge, seems to produce an infinite chain.

          SpiralTiling
          Image: An introduction to tilings. J.O'Rourke mods.
          Original MO: Radial tilings with variable area ratios . Grünbaum & Shephard.

1 Rhoads, Glenn C. "Planar tilings by polyominoes, polyhexes, and polyiamonds." Journal of Computational and Applied Mathematics 174, no. 2 (2005): 329-353. Journal link.

Improve this question
$\endgroup$
5
  • $\begingroup$ can such a graph have loops? $\endgroup$
    – Dima Pasechnik
    Commented Jun 20, 2019 at 20:39
  • $\begingroup$ @DimaPasechnik: Under my definition, there can be no loop, for then the tile would have to join with itself along a distinguished edge, and the tile would then not be a simple polygon. So that's a good point: No loops. Thanks! $\endgroup$
    – Joseph O'Rourke
    Commented Jun 20, 2019 at 20:42
  • $\begingroup$ it is tempting to say that all you can get is a collection of cycles and isolated edges. $\endgroup$
    – Dima Pasechnik
    Commented Jun 20, 2019 at 22:03
  • 1
    $\begingroup$ An edge between two vertices has to come from a copy of $e^*$ in one of the corresponding tiles. So any finite set of $n$ vertices can span at most $n$ edges, and consequently all you can get are disjoint unions of trees and unicyclic graphs (giving plenty of graphs that cannot be realised). $\endgroup$
    – Florian Lehner
    Commented Jun 21, 2019 at 10:30
  • $\begingroup$ @FlorianLehner: Thanks, that observation nearly characterizes the graphs. Thanks! $\endgroup$
    – Joseph O'Rourke
    Commented Jun 21, 2019 at 22:25

0

Reset to default

You must log in to answer this question.