Tiling pictures of the plane with dominoes
type: Item
instance of: scholarly article
title: Tiling pictures of the plane with dominoes
zbMATH Open document ID: 0877.05009
DOI: 10.1016/S0012-365X(96)00179-3
published in: Discrete Mathematics
publication date: 1997-07-20T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05B45
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68W10
Mathematics Subject Classification ID: 68W15
zbMATH DE Number: 1019104
zbMATH Keywords: tiling groups
zbMATH Keywords: tiling by dominoes
zbMATH Keywords: matching in bipartite graphs
zbMATH Keywords: breadth first search
author: Jean-Claude Fournier
MaRDI profile type: Publication
cites work: Tiling figures of the plane with two bars
cites work: Tiling with polyominoes and combinatorial group theory
cites work: Tiling of planar figures without gaps by dominos: graphical foundations of Thurston if algorithm, parallelization uniqueness and decomposion
cites work: An improved parallel algorithm that computes the BFS numbering of a directed graph
cites work: Tiling polygons with parallelograms
cites work: Q4228435
cites work: Q3880849
cites work: Q3727386
cites work: Conway's Tiling Groups
full work available at URL: s0012-365x(96)00179-3
OpenAlex ID: W2066227270
Wikidata QID: Q127333287
description: scientific article; zbMATH DE number 1019104