Graph encoding of 2D-gon tilings.

Frédéric Chavanon (1) , Matthieu Latapy (1) , Michel Morvan (1) , Laurent Vuillon (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

2D-gons tilings with parallelograms are the main model used in physics to study quasicrystals, and they are also important in combinatorics for the study of aperiodic structures. In this paper, we study the graph induced by the adjacency relation between tiles. This relation can been used to encode simply and efficiently 2D-gon tilings for algorithmic manipulation. We show for example how it can be used to sample random 2D-gon tilings.

Les pavages de 2D-gones par parallélogrammes sont un des principaux modèles de quasicristaux utilisés en physique, ainsi qu’en combinatoire pour l’ étude des structures a périodiques. Dans ce papier nous étudions le graphe induit par les relations d’adjacence entre tuiles. Cette relation est utilisée afin de coder les pavages de 2D-gones de façon simple et utilisable pour des manipulations algorithmiques. Nous montrons par exemple comment ce codage peut être exploité pour la génération aléatoire de pavages de 2D-gones.

Mots clés: Data structures; Quasicrystals; Tilings

Mots clés: Pavages; Quasicristaux; Combinatoire

Domaines: Informatique [cs]

Frédéric Chavanon, Matthieu Latapy, Michel Morvan, Laurent Vuillon. Graph encoding of 2D-gon tilings.. [Research Report] LIP RR-2003-43, Laboratoire de l'informatique du parallélisme. 2003, 2+17p. ⟨hal-02101899⟩