MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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. – Algernon Apr 25 '14 at 23:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.