Skip to Main content Skip to Navigation
Conference papers

Planar Dimer Tilings

Olivier Bodini 1 Thomas Fernique 2
2 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Document type :
Conference papers
Complete list of metadata
Contributor : Thomas Fernique <>
Submitted on : Friday, May 25, 2007 - 1:50:43 PM
Last modification on : Tuesday, January 12, 2021 - 9:36:03 AM
Long-term archiving on: : Thursday, April 8, 2010 - 5:53:10 PM



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⟩



Record views


Files downloads