title: Periodic graph (crystallography)
text: # Periodic graph (crystallography)
  
  In crystallography, a periodic graph or crystal net is a three-dimensional periodic graph, i.e., a three-dimensional Euclidean graph whose vertices or nodes are points in three-dimensional Euclidean space, and whose edges (or bonds or spacers) are line segments connecting pairs of vertices, periodic in three linearly independent axial directions. There is usually an implicit assumption that the set of vertices are uniformly discrete, i.e., that there is a fixed minimum distance between any two vertices. The vertices may represent positions of atoms or complexes or clusters of atoms such as single-metal ions, molecular building blocks, or secondary building units, while each edge represents a chemical bond or a polymeric ligand.
  
  Although the notion of a periodic graph or crystal net is ultimately mathematical (actually a crystal net is nothing but a periodic realization of an abelian covering graph over a finite graph ), and is closely related to that of a Tessellation of space (or honeycomb) in the theory of polytopes and similar areas, much of the contemporary effort in the area is motivated by crystal engineering and prediction (design), including metal-organic frameworks (MOFs) and zeolites.
  
  ## History
  
  A crystal net is an infinite molecular model of a crystal. Similar models existed in Antiquity, notably the atomic theory associated with Democritus, which was criticized by Aristotle because such a theory entails a vacuum, which Aristotle believed nature abhors. Modern atomic theory traces back to Johannes Kepler and his work on geometric packing problems. Until the twentieth century, graph-like models of crystals focused on the positions of the (atomic) components, and these pre-20th century models were the focus of two controversies in chemistry and materials science.
  
  The two controversies were (1) the controversy over Robert Boyle’s corpuscular theory of matter, which held that all material substances were composed of particles, and (2) the controversy over whether crystals were minerals or some kind of vegetative phenomenon. During the eighteenth century, Kepler, Nicolas Steno, René Just Haüy, and others gradually associated the packing of Boyle-type corpuscular units into arrays with the apparent emergence of polyhedral structures resembling crystals as a result. During the nineteenth century, there was considerably more work done on polyhedra and also of crystal structure, notably in the derivation of the Crystallographic groups based on the assumption that a crystal could be regarded as a regular array of unit cells. During the early twentieth century, the physics and chemistry community largely accepted Boyle's corpuscular theory of matter—by now called the atomic theory—and X-ray crystallography was used to determine the position of the atomic or molecular components within the unit cells (by the early twentieth century, unit cells were regarded as physically meaningful).
  
  However, despite the growing use of stick-and-ball molecular models, the use of graphical edges or line segments to represent chemical bonds in specific crystals have become popular more recently, and the publication of encouraged efforts to determine graphical structures of known crystals, to generate crystal nets of as yet unknown crystals, and to synthesize crystals of these novel crystal nets. The coincident expansion of interest in tilings and tessellations, especially those modeling quasicrystals, and the development of modern Nanotechnology, all facilitated by the dramatic increase in computational power, enabled the development of algorithms from computational geometry for the construction and analysis of crystal nets. Meanwhile, the ancient association between models of crystals and tessellations has expanded with Algebraic topology. There is also a thread of interest in the very-large-scale integration (VLSI) community for using these crystal nets as circuit designs.
  
  ## Basic formulation
  
  A Euclidean graph in three-dimensional space is a pair (V, E), where V is a set of vertices (sometimes called points or nodes) and E is a set of edges (sometimes called bonds or spacers) where each edge joins two vertices. 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.
  
  ### Symmetries and periodicity
  
  A symmetry of a Euclidean graph is an isometry of the underlying Euclidean space whose restriction to the graph is an automorphism; the symmetry group of the Euclidean graph is the group of its symmetries. A Euclidean graph in three-dimensional Euclidean space is periodic if there exist three linearly independent translations whose restrictions to the net are symmetries of the net. Often (and always, if one is dealing with a crystal net), the periodic net has finitely many orbits, and is thus uniformly discrete in that there exists a minimum distance between any two vertices.
  
  The result is a three-dimensional periodic graph as a geometric object.
  
  The resulting crystal net will induce a lattice of vectors so that given three vectors that generate the lattice, those three vectors will bound a unit cell, i.e. a parallelepiped which, placed anywhere in space, will enclose a fragment of the net that repeats in the directions of the three axes.
  
  ### Symmetry and kinds of vertices and edges
  
  Two vertices (or edges) of a periodic graph are symmetric if they are in the same orbit of the symmetry group of the graph; in other words, two vertices (or edges) are symmetric if there is a symmetry of the net that moves one onto the other. In chemistry, there is a tendency to refer to orbits of vertices or edges as “kinds” of vertices or edges, with the recognition that from any two vertices or any two edges (similarly oriented) of the same orbit, the geometric graph “looks the same”. Finite colorings of vertices and edges (where symmetries are to preserve colorings) may be employed.
  
  The symmetry group of a crystal net will be a (group of restrictions of a) crystallographic space group, and many of the most common crystals are of very high symmetry, i.e. very few orbits. A crystal net is uninodal if it has one orbit of vertex (if the vertices were colored and the symmetries preserve colorings, this would require that a corresponding crystal have atoms of one element or molecular building blocks of one compound – but not vice versa, for it is possible to have a crystal of one element but with several orbits of vertices). Crystals with uninodal crystal nets include cubic diamond and some representations of quartz crystals. Uninodality corresponds with isogonality in geometry and vertex-transitivity in graph theory, and produces examples objective structures. A crystal net is binodal if it has two orbits of vertex; crystals with binodal crystal nets include boracite and anatase. It is edge-transitive or isotoxal if it has one orbit of edges; crystals with edge-transitive crystal nets include boracite but not anatase – which has two orbits of edges.
  
  ### Geometry of crystal nets
  
  In the geometry of crystal nets, one can treat edges as line segments. For example, in a crystal net, it is presumed that edges do not “collide” in the sense that when treating them as line segments, they do not intersect. Several polyhedral constructions can be derived from crystal nets. For example, a vertex figure can be obtained by subdividing each edge (treated as a line segment) by the insertion of subdividing points, and then the vertex figure of a given vertex is the convex hull of the adjacent subdividing points (i.e., the convex polyhedron whose vertices are the adjacent subdividing points).
  
  Another polyhedral construction is to determine the neighborhood of a vertex in the crystal net. One application is to define an energy function as a (possibly weighted) sum of squares of distances from vertices to their neighbors, and with respect to this energy function, the net is in equilibrium (with respect to this energy function) if each vertex is positioned at the centroid of its neighborhood, this is the basis of the crystal net identification program SYSTRE. (mathematicians use the term ``harmonic realiaztions" instead of ``crystal nets in equilibrium positions" because the positions are characterized by the discrete Laplace equation; they also introduced the notion of standard realizations which are special harmonic realizations characterized by a certain minimal principle as well;see). Some crystal nets are isomorphic to crystal nets in equilibrium positions, and since an equilibrium position is a normal form, the crystal net isomorphism problem (i.e., the query whether two given crystal nets are isomorphic as graphs; not to be confused with crystal isomorphism) is readily computed even though, as a subsumption of the graph isomorphism problem, it is apparently computationally difficult in general.
  
  ## Active areas of crystal design using crystal nets
  
  It is conjectured that crystal nets may minimize entropy in the following sense. Suppose one is given an ensemble of uniformly discrete Euclidean graphs that fill space, with vertices representing atoms or molecular building blocks and with edges representing bonds or ligands, extending through all space to represent a solid. For some restrictions, there may be a unique Euclidean graph that minimizes a reasonably defined energy function, and the conjecture is that that Euclidean graph may necessarily be periodic. This question is still open, but some researchers observe crystal nets of high symmetry tending to predominate observed Euclidean graphs derived from some classes of materials.
  
  Historically, crystals were developed by experimentation, currently formalized as combinatorial chemistry, but one contemporary desideratum is the synthesis of materials designed in advance, and one proposal is to design crystals (the designs being crystal nets, perhaps represented as one unit cell of a crystal net) and then synthesize them from the design. This effort, in what Omar Yaghi described as reticular chemistry is proceeding on several fronts, from the theoretical to synthesizing highly porous crystals.
  
  One of the primary issues in annealing crystals is controlling the constituents, which can be difficult if the constituents are individual atoms, e.g., in zeolites, which are typically porous crystals primarily of silicon and oxygen and occasional impurities. Synthesis of a specific zeolite de novo from a novel crystal net design remains one of the major goals of contemporary research. There are similar efforts in sulfides and phosphates.
  
  Control is more tractable if the constituents are molecular building blocks, i.e., stable molecules that can be readily induced to assemble in accordance with geometric restrictions. Typically, while there may be many species of constituents, there are two main classes: somewhat compact and often polyhedral secondary building units (SBUs), and linking or bridging building units. A popular class of examples are the Metal-Organic Frameworks (MOFs), in which (classically) the secondary building units are metal ions or clusters of ions and the linking building units are organic ligands. These SBUs and ligands are relatively controllable, and some new crystals have been synthesized using designs of novel nets. An organic variant are the Covalent Organic Frameworks (COFs), in which the SBUs might (but not necessarily) be themselves organic. The greater control over the SBUs and ligands can be seen in the fact that while no novel zeolites have been synthesized per design, several MOFs have been synthesized from crystal nets designed for zeolite synthesis, such as Zeolite-like Metal-Organic Frameworks (Z-MOFs) and zeolitic imidazolate framework (ZIFs).
  
  