A Euclidean graph (a graph embedded in some Euclidean space) is periodic if there exists a basis of that Euclidean space whose corresponding translations induce symmetries of that graph (i.e., application of any such translation to the graph embedded in the Euclidean space leaves the graph unchanged). Equivalently, a periodic Euclidean graph is a periodic realization of an abelian covering graph over a finite graph. A Euclidean graph is uniformly discrete if there is a minimal distance between any two vertices. Periodic graphs are closely related to tessellations of space (or honeycombs) and the geometry of their symmetry groups, hence to geometric group theory, as well as to discrete geometry and the theory of polytopes, and similar areas. Much of the effort in periodic graphs is motivated by applications to natural science and engineering, particularly of three-dimensional crystal nets to crystal engineering, crystal prediction (design), and modeling crystal behavior. Periodic graphs have also been studied in modeling very-large-scale integration (VLSI) circuits.
Basic formulation A Euclidean graph is a pair (V, E), where V is a set of points (sometimes called vertices or nodes) and E is a set of edges (sometimes called bonds), where each edge joins two vertices. While an edge connecting two vertices u and v is usually interpreted as the set { u, v }, an edge is sometimes interpreted as the line segment connecting u and v so that the resulting structure is a CW complex. There is a tendency in the polyhedral and chemical literature to refer to geometric graphs as nets (contrast with polyhedral nets), and the nomenclature in the chemical literature differs from that of graph theory. Most of the literature focuses on periodic graphs that are uniformly discrete in that there exists e > 0 such that for any two distinct vertices, their distance apart is |u – v| > e. From the mathematical view, a Euclidean periodic graph is a realization of an infinite-fold abelian covering graph over a finite graph.
Obtaining periodicity The identification and classification of the crystallographic space groups took much of the nineteenth century, and the confirmation of the completeness of the list was finished by the theorems of Evgraf Fedorov and Arthur Schoenflies. The problem was generalized in David Hilbert's eighteenth Problem, and the Fedorov–Schoenflies Theorem was generalized to higher dimensions by Ludwig Bieberbach. The Fedorov–Schoenflies theorem asserts the following. Suppose that one is given a Euclidean graph in 3-space such that the following are true:
It is uniformly discrete in that there exists e > 0 such that for any two distinct vertices, their distance apart is |u – v| > e. It fills space in the sense that for any plane in 3-space, there exist vertices of the graph on both sides of the plane. Each vertex is of finite degree or valency. There are finitely many orbits of vertices under the symmetry group of the geometric graph. Then the Euclidean graph is periodic in that the vectors of translations in its symmetry group span the underlying Euclidean space, and its symmetry group is a crystallographic space group. The interpretation in science and engineering is that since a Euclidean graph representing a material extending through space must satisfy conditions (1), (2), and (3), non-crystalline substances from quasicrystals to glasses must violate (4). However, in the last quarter century, quasicrystals have been recognized to share sufficiently many chemical and physical properties with crystals that there is a tendency to classify quasicrystals as "crystals" and to adjust the definition of "crystal" accordingly.
Mathematics and computation Much of the theoretical investigation of periodic graphs has focused on the problems of generating and classifying them.
… excerpt ends here. Continue reading the full article.
