Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
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 at 23:45

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.