Planar Dimer Tilings - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2006

Planar Dimer Tilings


Domino tilings of finite domains of the plane are used to model dimer systems in statistical physics. In this paper, we study dimer tilings, which generalize domino tilings and are indeed equivalent to perfect matchings of planar graphs. We use height functions, a notion previously introduced by Thurston for domino tilings, to prove that a dimer tiling of a given domain can be computed using any Single-Source-Shortest-Paths algorithm on a planar graph. We also endow the set of dimers tilings of a given domain with a structure of distributive lattice and show that it can be effectively visited by a simple algorithmical operation called flip.
Fichier principal
Vignette du fichier
dimer_appendix.pdf (259.88 Ko) Télécharger le fichier

Dates and versions

lirmm-00149365 , version 1 (25-05-2007)



Olivier Bodini, Thomas Fernique. Planar Dimer Tilings. CSR 2006 - 1st International Computer Science Symposium in Russia, Jun 2006, St. Petersburg, Russia. pp.104-113, ⟨10.1007/11753728_13⟩. ⟨lirmm-00149365⟩
133 View
151 Download



Gmail Mastodon Facebook X LinkedIn More