2
$\begingroup$

We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution.

However, is there a well established counter-part graph theoretic representation for the 2 dimensional tiling problem?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ You could represent a set of 2d Wang tiles by a graph with two types of edges: horizontal and vertical. As in one dimension, tilings would correspond to graph homomorphisms (respecting edge types) from the graph of the lattice to the graph of the tiles. However, this representation does not make the complications in 2d go away, because the homomorphisms from the 2d lattice graph are not as simple as the homomorphisms from an infinite path. $\endgroup$
    – Algernon
    Commented Apr 25, 2014 at 23:45

0

Reset to default

You must log in to answer this question.