After introducing Delaney symbols by describing their construction for a twodimensional tiling, I will give a general characterization and review some of the most important mathematical results.
Please note that in the following, the edges and vertices of a tiling will be defined in a purely combinatorial way. Thus, in Dimension 2, a vertex is a point where at least three tiles meet. An edge is a portion of the common boundary of two tiles in between two vertices.
Consider the tiling shown in Figure 2. First, a barycentric subdivision is constructed as follows:
Ideally, the barycentric subdivision should be constructed as to retain the symmetry of the tiling. This is always possible. A closeup of Figure 2 together with its barycentric subdivision is shown in Figure 3.
Obviously, the barycentric subdivision is a triangulation. To avoid confusion, we will refer to its tiles as chambers. Each chamber has three types of vertices, namely one being an original vertex, one chosen inside an edge and one chosen inside a tile. We label these `0', `1' and `2', accordingly. There are also three types of edges. Edges are labelled the same as the vertices opposite to them. In Figure 3, edges labelled `0' are shown dashed, those labelled `1' are shown dotted, while edges labelled `2' are shown solid.
Each chamber has three neighbors, which are distinguished by the type of edge they share with it. Thus, any finite portion of the triangulation can be described completely by listing for each chamber its three neighbors in order. For a given chamber t, we will denote these by s_{0}(t), s_{1}(t) and s_{2}(t), respectively.
Next, we take symmetries into account. Two chambers are called symmetry equivalent if there is a symmetry of the tiling mapping one onto the other. In Figure 4, equivalent chambers are marked with a common letter. Clearly, there are 10 classes in this particular case, which bear the letters `A' up to `J'.
As corresponding neighbors of chambers in the same class belong to the same class again, we can assign to each class C its three ``neighboring'' classes s_{0}(C), s_{1}(C) and s_{2}(C), respectively, where the class s_{i}(C) consist of all the neighbors s_{i}(t) of chambers t in class C. The set of classes together with its neighborhood relations is called the Delaney set^{1}. It is convenient to envision the classes as nodes and the neighborhood relations as labelled edges of a graph. Consequently, the term Delaney graph is used as well. Note that the edges of the Delaney graph are undirected, because the neighborhood relations are reflective. Of course, the set of chambers of the barycentric subdivision can be regarded as a  possibly infinite  graph in the same way, which we will call the chamber graph.
It is always possible to choose a connected region containing one chamber of each type, as shown in gray in Figure 4. Such a region forms a particular fundamental domain for the tiling's symmetry group. A convenient way to explore the Delaney graph is to extract a fundamental domain together with its immedatiately surrounding chambers, as depicted in Figure 5.
Clearly, the Delaney graph alone does not uniquely determine the tiling. This becomes obvious when we consider the archimedean solid, or spherical tiling, depicted in Figure 6, which has exactly the same Delaney graph as our plane example, but contains squares instead of regular hexagons.
We augment the Delaney graph by assigning to each class C of chambers the two numbers m_{0}(C) and m_{1}(C). The first of these gives the degree, i.e., the number of vertices, of the faces containing chambers of this class, while the second gives the degree of the vertices adjacent to chambers of this class. By construction, neither of these numbers depends on the actual chamber chosen, so they are ``welldefined''. The augmented Delaney graph is called the Delaney symbol of the tiling in question. The Delaney symbol for the tiling in Figure 2 is shown in tabular form and as a labelled graph in Figure 7. The Delaney symbol for the archimedean solid of Figure 6, as a matter of fact, can be obtained by setting both m_{0}(A) and m_{0}(B) to 4 instead of 6.

Delaney symbols are insensitive to deformations of tilings as long as these change neither the topology nor the symmetries. More precisely, two tilings are said to be topologically equivalent if there is a homeomorphism  a bothways continuous transformation  mapping tiles of the first onto tiles of the second. It is said to be combinatorially equivalent if there is such a transformation which in addition maps (by conjugation) the symmetry group of the first to the symmetry group of the second. By construction, Delaney symbols are invariants of combinatorial equivalence classes. The first and most important theorem reviewed here states that they are even sharp invariants.
Two Delaney symbols are isomorphic if one can be obtained from the other just by renaming the nodes. This can be efficiently tested, as will be demonstrated below.
Theorem 1 remains true in higher dimensions, where the construction of the Delaney symbol is performed in an analoguous way. In fact, it holds true whenever both spaces tiled are simply connected manifolds. A manifold is anything that locally looks like an ordinary euclidean space, whereas a space is simply connected if every closed curve in it can be continuously deformed into a single point without leaving the space. An example of a manifold which is not simply connected is the surface of a doughnut, also called a torus.
Following is a characterization of ``formal'' Delaney symbols in arbitrary dimension, using those properties which are immediate from the construction.
For practical reasons, we will usually assume that Delaney symbols are finite. We will therefore restrict our attention to tilings which possess finite Delaney symbols, as periodic tilings do. We will refer to these as generalized periodic tilings. Among the generalized periodic tilings are tilings of spheres and also certain tilings of hyperbolic spaces.
The following notations will be useful:
Next, we consider how to determine whether a given formal Delaney symbol actually is derived from a tiling of, say, the euclidean plane. In dimension 2, this can be done using a simple numerical invariant:
To illustrate this, for the Delaney symbol in Figure 7, we have
whereas for the Delaney symbol of the archimedean solid shown in Figure 6, we have
Actually, the quantities v_{i, j}(C) and, if the curvature is positive, the number 4/K(C) as well, have important interpretations. The symmetry group of a spherical tiling with Delaney symbol C has exactly 4/K(C) elements. As is obvious from the definitions, a value of v_{i, j}(C) larger than 1 indicates a rotation of that order fixing the vertex  or, in general, the face of codimension 2  of any chamber in class C at the intersection of its two codimension 1 faces labelled i and j.
The proof of Theorem 5 relies on the Euler characteristic of surfaces. Since the Euler characteristic is always 0 in odd dimensions, no analogous result is available for threedimensional Delaney symbols. In [Del00], a partial algorithm is described for the recognition of Delaney symbols of threedimensional tilings.
Every face, i.e., in the twodimensional case, every vertex, edge and tile, of a tiling is represented by a unique vertex of its barycentric subdivision. This vertex is labelled i if it lies in an idimensional face. Two chambers t and t' share a common ivertex if and only if they lie in the same connected component of the graph obtained by removing all iedges from the chamber graph. These are exactly those chambers which have a nonempty intersection with the given face. This relationship carries over to the Delaney symbol, where symmetry equivalence classes of ifaces are represented by connected components of the partial Delaney graph obtained by removing all iedges.
These connected components are an important tool in combinatorial tiling theory, especially in dimensions 3 and higher. Together with the relevant `m'functions, we refer to them as subsymbols. An Isubsymbol of an ndimensional Delaney symbol C is defined by an element C C and a subset I {0,..., n}. It consists of all elements of C which can be reached from C by repeatedly applying only functions s_{i} with i I. A {0,..., n  1}subsymbol, for example, represents the combinatorial structure of a tile.
The Delaney symbol in Figure 7 contains the three {0, 1}subsymbols {A, B}, {C, D, E, F, G, H} and {I, J}.
To complete this section, let us consider tilings which are topologically, but not combinatorially equivalent. Figure 8 shows a simple tiling by squares and a topologically equivalent one by rectangles, both with barycentric subdivisions and letters marking respective chamber classes. In the rectangle tiling, the reflections at the diagonals are no longer symmetries of the tiling, so its Delaney symbol has two elements instead of just one in the case of the square tiling.
The rectangle tiling is called a symmetry breaking of the square tiling. There is a homeomorphism which maps tiles of the rectangle tiling onto tiles of the square tiling and symmetries of the rectangle tiling to symmetries of the square tiling, but not all symmetries of the square tiling are obtained in this way. Such a homeomorphism also takes chambers and chamber classes of the first tiling onto chambers and chamber classes of the second one, thereby inducing a wellbehaved mapping between their Delaney symbols, which we call a Delaney map or just a map.
Every isomorphism has a reverse map which is a Delaney map, which justifies its name. For finite Delaney symbols, a Delaney map is an isomorphism if both symbols have the same size. A finite Delaney symbol is minimal if it can not be mapped onto a smaller one.
If fCC^{} is a Delaney map and C^{} is the Delaney symbol of a tiling, then C is the Delaney symbol of a symmetry breaking of that tiling. If C corresponds to some tiling, then a tiling corresponding to C^{} would have to have more symmetries, which might not always be possible. It has been shown, however, that for all C corresponding to either a twodimensional or a euclidean threedimensional tiling, C^{} will correspond to a tiling of the same geometry [Del00].
As will be shown in the next section, there is for every Delaney symbol a unique minimal image, which can be computed efficiently. This means that, at least for twodimensional and euclidean threedimensional tilings, every topological equivalence class has a unique representative with maximal symmetry.