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.
Type de document :
Communication dans un congrès
CSR 2006 - 1st International Computer Science Symposium in Russia, Jun 2006, St. Petersburg, Russia. Springer, 3967, pp.104-113, 2006, Lecture Notes in Computer Science. 〈10.1007/11753728_13〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00149365
Contributeur : Thomas Fernique <>
Soumis le : vendredi 25 mai 2007 - 13:50:43
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : jeudi 8 avril 2010 - 17:53:10

Identifiants

Collections

Citation

Olivier Bodini, Thomas Fernique. Planar Dimer Tilings. CSR 2006 - 1st International Computer Science Symposium in Russia, Jun 2006, St. Petersburg, Russia. Springer, 3967, pp.104-113, 2006, Lecture Notes in Computer Science. 〈10.1007/11753728_13〉. 〈lirmm-00149365〉

Partager

Métriques

Consultations de la notice

140

Téléchargements de fichiers

90