On the generation and enumeration of tessellation designs

Tessellation designs composed from tiles in periodic space fillings are considered. An efficient algorithmic theory for the generation and enumeration of nonequivalent designs is developed. It is shown that each design has a graphical representation as a labelled subgraph of some graph whose vertices have associated integral coordinates. Detecting isomorphisms between designs then reduces to determining permutations of the labels of the vertices of this graph and may be performed in linear time. A proof of correctness for the algorithmic theory is provided. Nine specific algorithms for various families of designs from the archimedean tessellations are presented.