Tiling pictures of the plane with dominoes (Q1356753)

This report is concerned with the problem of tiling finite subsets of the square grid with \(( 2 \times 1 )\)-dominoes. Such tilings (and their existence) are closely related to height functions which essentially depend on the number of white and black squares along edge paths in a checkerboard colouring. For regions without holes, this characterization was first formulated by W.P. Thurston (using tiling groups), and translated into a graph theoretic context (matchings in bipartite graphs) by the author [\textit{J. C. Fournier}, Theor. Comput. Sci. 159, 105-128 (1996)]. In this paper, algorithmic aspects of the problem, and some extensions (such as sets with balanced holes---with respect to white and black squares---) are discussed. No proofs are given.