ドミノタイリング
ウィリアム・サーストン(William Thurston)は、1990年に平面内の単連結な領域が、単位四方形の組(ドミノ)によりドミノタイリングとして形成されるか否かを決定できることを著した。彼は、3次元の整数格子(英語版)(integer lattice)の中の点 (x,y,z) を頂点として持つような無向グラフを作った。そこでは各々の点が 4つの近傍に連結していて、x+y が偶数であれば、(x,y,z) は (x+1,y,z+1), (x-1,y,z+1), (x,y+1,z-1), (x,y-1,z-1) と連結し、一方、x+y が奇数であれば、(x,y,z) は (x+1,y,z-1), (x-1,y,z-1), (x,y+1,z+1), (x,y-1,z+1) と連結している。この領域の境界は、(x,y) 平面の中の整数の点の列として見なすと、この一意に 3次元グラフ(three-dimensional graph)の中の経路へ(一度、初期の高さを決めると)持ち上げることができる。この領域がタイリング可能であるための必要条件は、この経路が 3次元で単純な閉曲線を形成することを除いて閉じている必要がある。しかし、この条件だけでは充分でない。境界の経路のより注意深く解析して、サーストンは必要かつ充分な領域のタイリングの可能性の判定条件を与えた。