Planar Dimer Tilings - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2006

Planar Dimer Tilings

Résumé

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 et versions

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

Identifiants

Citer

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⟩
130 Consultations
146 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More