Some very interesting types of tiling problems have a trivial graph. For example, the Wang tiling problem uses square tiles, which are labeled on the sides, and the rule for the tiling is that the labels must match. (So the graph is just the integer lattice.) One of the most interesting things about this type of tiling is that the question of whether a given finite set of tile types admits a tiling is undecidable. That is, there can in principal be no computation computational algorithm that will correctly determine whether a given finite set of tiles admits a tiling. The reason for this is that the operation of Turing machines is encodable into these tiling problems: for any Turing machine program p, one can uniformly construct a finite set of tiles that admits a tiling if and only if this program halts (on input 0, say). Basically, the pattter patttern of tiling can continue to tile the plane as long as the Turing computation doesn't halt, but a halting computation messes up the existence of a tiling.
However, one can encode many or most of the usual geometric tile problems into these wang tiles, by dividing each geometric figure into square pixels, which must be matches together. So in a strong sense, any geometric tiling problem reduces to an instance of a Wang tiling problem. Thus, the general geometric tiling problem is also undecidable.
