We know that any closed cycle of a graph could be decomposed into sum of simple cycles. To translate this theorem into tiling of 1D (Wang tile). We know that any 1D periodic tiling could be represented as a sum of basis tiling (correspondingly simple cycles).


However, in 2D, the tiling problem could be represented as a graph with 2 different kinds of edges:


[Graph theoretical representation of Wang Tile](https://mathoverflow.net/questions/164382/graph-theoretical-representation-of-wang-tile)


Question:
For any given graph with 2 kinds directed edges, is there some sort of simple 2D cycles? Such that any 2D cycles could be decomposed into sums of basis cycles?



simple cycle analog in 2D (with application in tiling)
I don't understand the graph theoretical representation you're talking about. (In particular, where do you put the information of which tiles are in the tile set?) So I'm going to interpret the question as follows:


Given a set of Wang tiles, is there a finite set $\mathcal B$ of periodic tilings such that for every periodic tiling $T$ and every tile $t$ in $T$, there is a periodic tiling $B \in \mathcal B$ such that some connected fundamental domain of $B$ appears in $T$ and includes $t$?


This is, as you mentioned, true in one dimension, since a one-dimensional set of Wang tiles corresponds to a directed graph, and a periodic tiling corresponds to a cycle in this graph. Given any cycle, each of its edges belongs to some simple cycle.


It is not true in two dimensions.


Take an aperiodic tile set, and add three new colors, red, blue, and black, and two types of new tiles:


(1) Red on the left and right, black on top, and any of the old colors on the bottom.


(2) Blue on the left and right, black on the bottom, and any of the old colors on top.


Because the original tile set is aperiodic, every periodic tiling with the new tile set has at least one of the new tiles, which implies it has a horizontal black line. However, there are periodic tilings with arbitrarily large vertical spacing between the black lines.


To see this, start with any (non-periodic, of course) tiling of the plane by old tiles and restrict attention to a height $N$ horizontal strip. Since there are finitely many vertical rows of colors in this strip, some vertical row must occur twice. Restrict attention to the rectangle between those occurrences, and put a row of the new tiles on the top and bottom. The resulting rectangle can be repeated to fill the entire plane, and its horizontal black lines are $N+2$ tiles apart.


Any finite set $\mathcal B$ of periodic tilings has an upper bound on how far a tile can be from one of the new tiles. In a periodic tiling with a big space between two black lines, a tile far away from either line cannot belong to a connected fundamental domain of a tile in $\mathcal B$.


