R70-9 A Graph-Theoretic Model for Periodic Discrete Structures

Wiring schemes which exploit the potential of modern integrated circuit technology are likely to exhibit a high degree of " periodicity," as well as various other attributes. The first contribution of this paper is to formulate a precise definition of periodicity in terms of a graph-theoretic model originated by Yoeli. Roughly speaking, an infinite graph is said to be periodic if it can be generated from a finite template which is moved (periodically) from point to point in the plane. This definition is interesting and useful, and generalizes nicely to infinite graphs in n-space.