Skip to main content
deleted 12 characters in body; added 1 character in body
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

Let $\cal T$ be a monohedral, edge-to-edge tiling of the plane, with prototile prototile $T$ a simple polygon, and with one edge $e^*$ of $T$ distinguished. Associate Associate a graph $G=G_{\cal T}$ with $\cal T$ as follows. Each 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 edge of either tile.

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


          [![PentagonTiling][1]][1]
          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. Because there seems to be considerable freedom to "design" $G$ when 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 distinguished edge, seems to produce an infinite chain.


          [![SpiralTiling][2]][2]
          Image: [An introduction to tilings](http://pi.math.cornell.edu/~mec/2008-2009/KathrynLindsey/PROJECT/homepage.html). J.O'Rourke mods.
          Original MO: [Radial tilings with variable area ratios ](https://mathoverflow.net/a/83148/6094). 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.

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][1]][1]
          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][2]][2]
          Image: [An introduction to tilings](http://pi.math.cornell.edu/~mec/2008-2009/KathrynLindsey/PROJECT/homepage.html). J.O'Rourke mods.
          Original MO: [Radial tilings with variable area ratios ](https://mathoverflow.net/a/83148/6094). 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.

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][1]][1]
          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][2]][2]
          Image: [An introduction to tilings](http://pi.math.cornell.edu/~mec/2008-2009/KathrynLindsey/PROJECT/homepage.html). J.O'Rourke mods.
          Original MO: [Radial tilings with variable area ratios ](https://mathoverflow.net/a/83148/6094). 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.

added 47 characters in body
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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][1]][1]
          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][2]][2]
          Image: [An introduction to tilings](http://pi.math.cornell.edu/~mec/2008-2009/KathrynLindsey/PROJECT/homepage.html). J.O'Rourke mods.
          Original MO: [Radial tilings with variable area ratios ](https://mathoverflow.net/a/83148/6094). 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.

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. Note that $G$ depends on both $T$ and $e^*$:


          [![PentagonTiling][1]][1]
          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][2]][2]
          Image: [An introduction to tilings](http://pi.math.cornell.edu/~mec/2008-2009/KathrynLindsey/PROJECT/homepage.html). J.O'Rourke mods.
          Original MO: [Radial tilings with variable area ratios ](https://mathoverflow.net/a/83148/6094). 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.

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][1]][1]
          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][2]][2]
          Image: [An introduction to tilings](http://pi.math.cornell.edu/~mec/2008-2009/KathrynLindsey/PROJECT/homepage.html). J.O'Rourke mods.
          Original MO: [Radial tilings with variable area ratios ](https://mathoverflow.net/a/83148/6094). 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.

deleted 8 characters in body
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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. Note that $G$ depends on both $T$ and $e^*$:


          [![PentagonTiling][1]][1]
          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][2]][2]
          Image: [An introduction to tilings](http://pi.math.cornell.edu/~mec/2008-2009/KathrynLindsey/PROJECT/homepage.html). J.O'Rourke mods.
          Original MO: [Radial tilings with variable area ratios ](https://mathoverflow.net/a/83148/6094). 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](https://www.sciencedirect.com/science/article/pii/S0377042704002195).

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.

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. Note that $G$ depends on both $T$ and $e^*$:


          [![PentagonTiling][1]][1]
          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][2]][2]
          Image: [An introduction to tilings](http://pi.math.cornell.edu/~mec/2008-2009/KathrynLindsey/PROJECT/homepage.html). J.O'Rourke mods.
          Original MO: [Radial tilings with variable area ratios ](https://mathoverflow.net/a/83148/6094). 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](https://www.sciencedirect.com/science/article/pii/S0377042704002195).

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. Note that $G$ depends on both $T$ and $e^*$:


          [![PentagonTiling][1]][1]
          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][2]][2]
          Image: [An introduction to tilings](http://pi.math.cornell.edu/~mec/2008-2009/KathrynLindsey/PROJECT/homepage.html). J.O'Rourke mods.
          Original MO: [Radial tilings with variable area ratios ](https://mathoverflow.net/a/83148/6094). 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.

added 39 characters in body
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958
Loading
added 157 characters in body
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958
Loading
added 431 characters in body
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958
Loading
Source Link
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958
Loading