# Graphs, Kites and Darts

**Non-periodic tilings with Penrose’s kites and darts**

We continue our investigation of the tilings using Haskell with Haskell Diagrams. What is new is the introduction of a planar graph representation. This allows us to define more operations on finite tilings, in particular **forcing** and **composing**.

Previously in Diagrams for Penrose Tiles we implemented tools to create and draw finite patches of Penrose kites and darts (such as the samples depicted in figure 1). The code for this and for the new graph representation and tools described here can be found on GitHub https://github.com/chrisreade/PenroseKiteDart.

To describe the tiling operations it is convenient to work with the half-tiles: `LD`

(left dart), `RD`

(right dart), `LK`

(left kite), `RK`

(right kite) using a polymorphic type `HalfTile`

(defined in a module `HalfTile`

)

```
data HalfTile rep
= LD rep | RD rep | LK rep | RK rep deriving (Show,Eq)
```

Here `rep`

is a type variable for a representation to be chosen. For drawing purposes, we chose two-dimensional vectors (`V2 Double`

) and called these `Pieces`

.

`type Piece = HalfTile (V2 Double)`

The vector represents the join edge of the half tile (see figure 2) and thus the scale and orientation are determined (the other tile edges are derived from this when producing a diagram).

Finite tilings or *patches* are then lists of located pieces.

`type Patch = [Located Piece]`

Both `Piece`

and `Patch`

are made transformable so `rotate`

, and `scale`

can be applied to both and `translate`

can be applied to a `Patch`

. (Translate has no effect on a `Piece`

unless it is located.)

In Diagrams for Penrose Tiles we also discussed the rules for legal tilings and specifically the problem of *incorrect tilings* which are legal but get stuck so cannot continue to infinity. In order to create *correct tilings* we implemented the `decompose`

operation on patches.

The vector representation that we use for drawing is not well suited to exploring properties of a patch such as neighbours of pieces. Knowing about neighbouring tiles is important for being able to reason about composition of patches (inverting a decomposition) and to find which pieces are determined (*forced*) on the boundary of a patch.

However, the polymorphic type `HalfTile`

allows us to introduce our alternative graph representation alongside `Piece`

s.

# Tile Graphs

In the module `Tgraph`

, we have the new representation which treats half tiles as triangular faces of a planar graph – a `TileFace`

– by specialising `HalfTile`

with a triple of vertices (clockwise starting with the tile origin). For example

`LD (1,3,4) RK (6,4,3)`

```
type Vertex = Int
type TileFace = HalfTile (Vertex,Vertex,Vertex)
```

When we need to refer to particular vertices from a `TileFace`

we use `originV`

(the first vertex – red dot in figure 2), `oppV`

(the vertex at the opposite end of the join edge – dashed edge in figure 2), `wingV`

(the remaining vertex not on the join edge).

`originV, oppV, wingV :: TileFace -> Vertex`

**Tgraphs**

The *Tile Graphs* implementation uses a type `Tgraph`

which has a list of graph vertices and a list of tile faces.

```
data Tgraph = Tgraph { vertices :: [Vertex]
, faces :: [TileFace]
} deriving (Show)
```

For example, `fool`

(short for a fool’s kite) is a `Tgraph`

with 6 faces and 7 vertices, shown in figure 3.

```
fool = Tgraph { vertices = [1,2,3,4,5,6,7]
, faces = [RD (1,2,3),LD (1,3,4),RK (6,2,5)
,LK (6,3,2),RK (6,4,3),LK (6,7,4)
]
}
```

(The fool is also called an *ace* in the literature)

With this representation we can investigate how composition works with whole patches. Figure 4 shows a twice decomposed sun on the left and a once decomposed sun on the right (both with vertex labels). In addition to decomposing the right graph to form the left graph, we can also compose the left graph to get the right graph.

After implementing composition, we also explore a *force* operation and an *emplace* operation to extend tilings.

There are some constraints we impose on `Tgraph`

s.

*No spurious vertices*. Every vertex of a`Tgraph`

face must be one of the`Tgraph`

vertices and each of the`Tgraph`

vertices occurs in at least one of the`Tgraph`

faces.*Connected*. The collection of faces must be a single connected component.*No crossing boundaries*. By this we mean that vertices on the boundary are incident with exactly two boundary edges. The boundary consists of the edges between the`Tgraph`

faces and exterior region(s). This is important for adding faces.*Face connected*. Roughly, this means that if we collect the faces of a`Tgraph`

by starting from any single face and then add faces which share an edge with those already collected, we get all the`Tgraph`

faces. This is important for drawing purposes.

In fact, if a `Tgraph`

is *connected* with *no crossing boundaries*, then it must be *face connected*. (We could define *face connected* to mean that the dual graph excluding exterior regions is connected.)

Figure 5 shows two excluded graphs which have crossing boundaries at 4 (left graph) and 13 (right graph). The left graph is still face connected but the right is not face connected (the two faces at the top right do not have an edge in common with the rest of the faces.)

Although we have allowed for `Tgraphs`

with holes (multiple exterior regions), we note that such holes cannot be created by adding faces one at a time without creating a crossing boundary. They can be created by removing faces from a `Tgraph`

without necessarily creating a crossing boundary.

**Important** We are using *face* as an abbreviation for half-tile face of a `Tgraph`

here, and we do not count the exterior of a patch of faces to be a face. The exterior can also be disconnected when we have holes in a patch of faces and the holes are not counted as faces either. In graph theory, the term *face* would generally include these other regions, but we will call them *exterior regions* rather than faces.

In addition to the constructor `Tgraph`

we also use

`checkTgraph:: [TileFace] -> Tgraph`

which creates a `Tgraph`

from a list of faces, but also performs checks on the required properties of `Tgraph`

s. We can then remove or select faces from a `Tgraph`

and then use `checkTgraph`

to ensure the resulting `Tgraph`

still satisfies the required properties.

```
selectFaces, removeFaces :: [TileFace] -> Tgraph -> Tgraph
selectFaces fcs g = checkTgraph (faces g `intersect` fcs)
removeFaces fcs g = checkTgraph (faces g \\ fcs)
```

**Edges and Directed Edges**

We do not explicitly record edges as part of a Tgraph, but calculate them as needed. Implicitly we are requiring

*No spurious edges*. The edges of a`Tgraph`

are the edges of the faces of the`Tgraph`

.

To represent edges, a pair of vertices (a,b) is regarded as a *directed* edge from a to b. A list of such pairs will usually be regarded as a *directed* edge list. In the special case that the list is symmetrically closed [(b,a) is in the list whenever (a,b) is in the list] we will refer to this as an *edge list* rather than a directed edge list.

The following functions on `TileFace`

s all produce directed edges (going clockwise round a face).

```
-- join edge - dashed in figure 2
joinE :: TileFace -> (Vertex,Vertex)
-- the short edge which is not a join edge
shortE :: TileFace -> (Vertex,Vertex)
-- the long edge which is not a join edge
longE :: TileFace -> (Vertex,Vertex)
-- all three directed edges clockwise from origin
faceDedges :: TileFace -> [(Vertex,Vertex)]
```

For the whole `Tgraph`

, we often want a list of all the directed edges of all the faces.

```
graphDedges :: Tgraph -> [(Vertex,Vertex)]
graphDedges g = concatMap faceDedges (faces g)
```

Because our graphs represent tilings they are planar (can be embedded in a plane) so we know that at most two faces can share an edge and they will have opposite directions of the edge. *No two faces can have the same directed edge*. So from `graphDedges g`

we can easily calculate internal edges (edges shared by 2 faces) and boundary directed edges (directed edges round the external regions).

`internalEdges, boundaryDedges :: Tgraph -> [(Vertex,Vertex)]`

The internal edges of `g`

are those edges which occur in both directions in `graphDedges g`

. The boundary directed edges of `g`

are the missing reverse directions in `graphDedges g`

.

We also refer to all the long edges of a `Tgraph`

(including kite join edges) as `phiEdges`

(both directions of these edges).

`phiEdges :: Tgraph -> [(Vertex, Vertex)]`

This is so named because, when drawn, these long edges are `phi`

times the length of the short edges (`phi`

being the golden ratio which is approximately 1.618).

# Drawing Tgraphs (Patches and VPatches)

The module `GraphConvert`

contains functions to convert a `Tgraph`

to our previous vector representation (`Patch`

) defined in `TileLib`

so we can use the existing tools to produce diagrams.

```
makePatch :: Tgraph -> Patch
drawPatch :: Patch -> Diagram B -- defined in module TileLib
drawGraph :: Tgraph -> Diagram B
drawGraph = drawPatch . makePatch
```

However, it is also useful to have an intermediate stage (a `VPatch`

= Vertex Patch) which contains both face (vertices) and vectors. This allows vertex labels to be drawn and for faces to be identified and retained/excluded after the vector information is calculated.

```
data VPatch = VPatch {lVertices :: [Located Vertex]
,lHybrids :: [Located Hybrid]
}
```

A `Vpatch`

has a list of located vertices and a list of located hybrids, where a `Hybrid`

is a `HalfTile`

with a dual representation of the face (vertices) and vector (join edge). We make `VPatch`

transformable so it can also be an argument type for `rotate`

, `translate`

, and `scale`

.

The conversion functions include

```
makeVPatch :: Tgraph -> VPatch
dropVertices :: VPatch -> Patch -- discards vertex information
drawVPatch :: VPatch -> Diagram B -- draws labels as well
drawVGraph :: Tgraph -> Diagram B
drawVGraph = drawVPatch . makeVPatch
```

One consequence of using abstract graphs is that there is no unique predefined way to orient or scale or position the patch arising from a graph representation. Our implementation selects a particular join edge and aligns it along the x-axis (unit length for a dart, `phi`

length for a kite) and face-connectedness ensures the rest of the patch can be calculated from this.

We also have functions to re-orient a `Vpatch`

and lists of `VPatch`

s using chosen pairs of vertices. [Simply doing rotations on the final diagrams can cause problems if these include vertex labels. We do not, in general, want to rotate the labels – so we need to orient the `Vpatch`

before converting to a diagram]

# Decomposing Graphs

We previously implemented decomposition for patches which splits each half-tile into two or three smaller scale half-tiles.

`decompose :: Patch -> Patch`

We now have a `Tgraph`

version of decomposition in the module `Tgraphs`

:

`decomposeG :: Tgraph -> Tgraph`

Graph decomposition is particularly simple. We start by introducing one new vertex for each long edge (the `phiEdges`

) of the Tgraph. We then build the new faces from each old face using the new vertices.

As a running example we take `fool`

(mentioned above) and its decomposition `foolD`

```
*Main> foolD = decomposeG fool
*Main> foolD
Tgraph { vertices = [1,8,3,2,9,4,5,13,10,6,11,14,7,12]
, faces = [LK (1,8,3),RD (2,3,8),RK (1,3,9)
,LD (4,9,3),RK (5,13,2),LK (5,10,13)
,RD (6,13,10),LK (3,2,13),RK (3,13,11)
,LD (6,11,13),RK (3,14,4),LK (3,11,14)
,RD (6,14,11),LK (7,4,14),RK (7,14,12)
,LD (6,12,14)
]
}
```

which are best seen together (`fool`

followed by `foolD`

) in figure 6.

# Composing graphs, and Unknowns

Composing is meant to be an inverse to decomposing, and one of the main reasons for introducing our graph representation. In the literature, decomposition and composition are defined for infinite tilings and in that context they are unique inverses to each other. For finite patches, however, we will see that composition is not always uniquely determined.

In figure 7 (Two Levels) we have emphasised the larger scale faces on top of the smaller scale faces.

How do we identify the composed tiles? We start by classifying vertices which are at the wing tips of the (smaller) darts as these determine how things compose. In the interior of a graph/patch (e.g in figure 7), a dart wing tip always coincides with a second dart wing tip, and either

- the 2 dart halves share a long edge. The shared wing tip is then classified as a
`largeKiteCentre`

and is at the centre of a larger kite. (See left vertex type in figure 8), or - the 2 dart halves touch at their wing tips without sharing an edge. This shared wing tip is classified as a
`largeDartBase`

and is the base of a larger dart. (See right vertex type in figure 8)

[We also call these (respectively) a deuce vertex type and a jack vertex type later in figure 10]

Around the boundary of a graph, the dart wing tips may not share with a second dart. Sometimes the wing tip has to be classified as `unknown`

but often it can be decided by looking at neighbouring tiles. In this example of a four times decomposed sun (`sunD4`

), it is possible to classify all the dart wing tips as largeKiteCentres or largeDartBases so there are no unknowns.

If there are no unknowns, then we have a function to produce the unique composed graph.

`composeG:: Tgraph -> Tgraph`

Any correct decomposed graph without unknowns will necessarily compose back to its original. This makes `composeG`

a left inverse to `decomposeG`

provided there are no unknowns.

For example, with an (`n`

times) decomposed sun we will have no unknowns, so these will all compose back up to a sun after `n`

applications of `composeG`

. For `n=4`

(`sunD4`

– the smaller scale shown in figure 7) the dart wing classification returns 70 `largeKiteCentres`

, 45 `largeDartBases`

, and no `unknowns`

.

Similarly with the simpler `foolD`

example, if we classsify the dart wings we get

```
largeKiteCentres = [14,13]
largeDartBases = [3]
unknowns = []
```

In `foolD`

(the right hand graph in figure 6), nodes 14 and 13 are new kite centres and node 3 is a new dart base. There are no unknowns so we can use `composeG`

safely

```
*Main> composeG foolD
Tgraph { vertices = [1,2,3,4,5,6,7]
, faces = [RD (1,2,3),LD (1,3,4),RK (6,2,5)
,RK (6,4,3),LK (6,3,2),LK (6,7,4)
]
}
```

which reproduces the original `fool`

(left hand graph in figure 6).

However, if we now check out unknowns for `fool`

we get

```
largeKiteCentres = []
largeDartBases = []
unknowns = [4,2]
```

So both nodes 2 and 4 are unknowns. It had looked as though `fool`

would simply compose into two half kites back-to-back (sharing their long edge not their join), but the unknowns show there are other possible choices. Each unknown could become a `largeKiteCentre`

or a `largeDartBase`

.

The question is then what to do with unknowns.

# Partial Compositions

In fact our `composeG`

resolves two problems when dealing with finite patches. One is the unknowns and the other is critical missing faces needed to make up a new face (e.g the absence of any half dart).

It is implemented using an intermediary function for partial composition

`partCompose:: Tgraph -> ([TileFace],Tgraph) `

`partCompose`

will compose everything that is uniquely determined, but will leave out faces round the boundary which cannot be determined or cannot be included in a new face. It returns the faces of the argument graph that were not used, along with the composed graph.

Figure 9 shows the result of `partCompose`

applied to two graphs. [These are `force kiteD3`

and `force dartD3`

on the left. Force is described later]. In each case, the excluded faces of the starting graph are shown in pale green, overlaid by the composed graph on the right.

Then `composeG`

is simply defined to keep the composed faces and ignore the unused faces produced by `partCompose`

.

```
composeG:: Tgraph -> Tgraph
composeG = snd . partCompose
```

This approach avoids making a decision about unknowns when composing, but it may lose some information by throwing away the uncomposed faces.

For correct `Tgraph`

s `g`

, if `decomposeG g`

has no unknowns, then `composeG`

is a left inverse to `decomposeG`

. However, if we take `g`

to be two kite halves sharing their long edge (not their join edge), then these decompose to `fool`

which produces an empty graph when recomposed. Thus we do not have `g = composeG (decomposeG g)`

in general. On the other hand we do have `g = composeG (decomposeG g)`

for correct *whole-tile* Tgraphs `g`

(*whole-tile* means all half-tiles of `g`

have their matching half-tile on their join edge in `g`

)

Later (figure 21) we show another exception to `g = composeG(decomposeG g)`

with an incorrect tiling.

We make use of

```
selectFacesVP :: [TileFace] -> VPatch -> VPatch
removeFacesVP :: [TileFace] -> VPatch -> VPatch
selectFacesGtoVP :: [TileFace] -> Tgraph -> VPatch
removeFacesGtoVP :: [TileFace] -> Tgraph -> VPatch
```

for creating `VPatch`

es from selected tile faces of a `Tgraph`

or `VPatch`

. This allows us to represent and draw a subgraph which need not be connected nor satisfy the no crossing boundaries property provided the `Tgraph`

it was derived from had these properties.

# Forcing

When building up a tiling, following the rules, there is often no choice about what tile can be added alongside certain tile edges at the boundary. Such additions are *forced* by the existing patch of tiles and the rules. For example, if a half tile has its join edge on the boundary, the unique mirror half tile is the only possibility for adding a face to that edge. Similarly, the short edge of a left (respectively, right) dart can only be matched with the short edge of a right (respectively, left) kite. We also make use of the fact that only 7 types of vertex can appear in (the interior of) a patch, so on a boundary vertex we sometimes have enough of the faces to determine the vertex type. These are given the following names in the literature (shown in figure 10): sun, star, jack (=largeDartBase), queen, king, ace, deuce (=largeKiteCentre).

The function

`force :: Tgraph -> Tgraph`

will add some faces on the boundary that are *forced* (i.e new faces where there is exactly one possible choice). For example:

- When a join edge is on the boundary – add the missing half tile to make a whole tile.
- When a half dart has its short edge on the boundary – add the half kite that must be on the short edge.
- When a vertex is both a dart origin and a kite wing (it must be a queen or king vertex) – if there is a boundary short edge of a kite half at the vertex, add another kite half sharing the short edge, (this converts 1 kite to 2 and 3 kites to 4 in combination with the first rule).
- When two half kites share a short edge their common
`oppV`

vertex must be a deuce vertex – add any missing half darts needed to complete the vertex. - …

Figure 11 shows `foolDminus`

(which is `foolD`

with 3 faces removed) on the left and the result of forcing, ie `force foolDminus`

on the right which is the same graph we get from `force foolD`

.

```
foolDminus =
removeFaces [RD(6,14,11), LD(6,12,14), RK(5,13,2)] foolD
```

Figures 12, 13 and 14 illustrate the the result of forcing a 5-times decomposed kite, a 5-times decomposed dart, and a 5-times decomposed sun (respectively). The first two figures reproduce diagrams from an article by Roger Penrose illustrating the extent of influence of tiles round a decomposed kite and dart. [Penrose R *Tilings and quasi-crystals; a non-local growth problem?* in Aperiodicity and Order 2, edited by Jarich M, Academic Press, 1989. (fig 14)].

In figure 15, the bottom row shows successive decompositions of a dart (dashed blue arrows from right to left), so applying `composeG`

to each dart will go back (green arrows from left to right). The black vertical arrows are `force`

. The solid blue arrows from right to left are `(force . decomposeG)`

being applied to the successive forced graphs. The green arrows in the reverse direction are `composeG`

again and the intermediate (`partCompose`

) figures are shown in the top row with the ignored faces in pale green.

Figure 16 shows the forced graphs of the seven vertex types (with the starting graphs in red) along with a kite (top right).

These are related to each other as shown in the columns. Each graph composes to the one above (an empty graph for the ones in the top row) and the graph below is its forced decomposition. [The rows have been scaled differently to make the vertex types easier to see.]

# Adding Faces to a Tgraph

This is technically tricky because we need to discover what vertices (and implicitly edges) need to be newly created and which ones already exist in the `Tgraph`

. This goes beyond a simple graph operation and requires use of the geometry of the faces. We have chosen not to do a full conversion to vectors to work out all the geometry, but instead we introduce a local representation of relative directions of edges at a vertex allowing a simple equality test.

**Edge directions**

All directions are integer multiples of 1/10th turn (`mod`

10) so we use these integers for comparing directions. The face adding process always adds to the right of a given directed edge `(a,b)`

which must be a boundary directed edge. [Adding to the left of an edge `(a,b)`

would mean that `(b,a)`

will be the boundary direction and so we are really adding to the right of `(b,a)`

]. Face adding looks to see if either of the two other edges already exist in the graph by considering the end points `a`

and `b`

to which the new face is to be added, and inspecting edges of existing faces at `a`

going anti-clockwise from `(a,b)`

and at `b`

going clockwise from `(b,a)`

.

This allows an edge in a particular sought direction to be discovered. If it is not found it is assumed not to exist. However, the search will be undermined, and will report a **crossing boundaries** error if a gap (= second boundary edge) is encountered *before* all the faces at the vertex are accounted for. In this case there must be more than two boundary directed edges at the vertex and it is unsafe to assume the edge being sought is not already present in the Tgraph.

Establishing the *no crossing boundaries* property ensures these failures cannot occur. We can easily check this property for newly created graphs (with `checkTgraph`

) and the face adding operations cannot create crossing boundaries.

**Touching Vertices and Crossing Boundaries**

When a new face to be added on `(a,b)`

has neither of the other two edges already in the graph, the third vertex needs to be created. However it could already exist in the `Tgraph`

– it is not on an edge coming from `a`

or `b`

but from another non-local part of the `Tgraph`

. We call this a *touching vertex*. If we simply added a new vertex without checking for a clash this would create a nonsense graph. However, if we do check and find an existing vertex, we still cannot add the face using this because it would create a crossing boundary.

Our version of forcing prevents face additions that would create a touching vertex/crossing boundary by calculating the positions of boundary vertices.

**No conflicting edges**

There is a final (simple) check when adding a new face, to prevent a long edge (`phiEdge`

) sharing with a short edge. This can arise if we force an incorrect graph (as we will see later).

# Implementing Forcing

Our order of forcing prioritises updates (face additions) which do not introduce a new vertex. Such *safe* updates are easy to recognise and they do not require a touching vertex check. Surprisingly, this pretty much removes the problem of touching vertices altogether.

As an illustration, consider `foolDMinus`

again on the left of figure 11. Adding the left dart onto edge `(12,14)`

is not a safe addition (and would create a crossing boundary at 6). However, adding the right dart `RD(6,14,11)`

is safe and creates the new edge (6,14) which then makes the left dart addition safe. In fact it takes some contrivance to come up with a `Tgraph`

with an update that could fail the check during forcing when safe cases are always done first. Figure 17 shows such a contrived `Tgraph`

formed by removing the faces shown in green from a twice decomposed sun on the left. The forced result is shown on the right. When there are no safe cases, we need to try an unsafe one. The four green faces at the bottom are blocked by the touching vertex check. This leaves any one of 9 half-kites at the centre which would pass the check. But after just one of these is added, the check is not needed again. There is always a safe addition to be done at each step until all the green faces are added.

**Boundary information**

The implementation of forcing has been made more efficient by calculating some boundary information in advance. This boundary information uses a type `Boundary`

```
data Boundary
= Boundary
{ bDedges :: [(Vertex,Vertex)]
, vFaceAssoc :: AssocList Vertex [TileFace]
, vPointAssoc :: AssocList Vertex (Point V2 Double)
, allFaces :: [TileFace]
, allVertices :: [Vertex]
, nextVertex :: Vertex
} deriving (Show)
```

This records the boundary directed edges (`bDedges`

) plus an association list of the faces incident with each boundary vertex (`vFaceAssoc`

) plus an association list with the position of each boundary vertex (`vPointAssoc`

). It also keeps track of all the faces and vertices. The boundary information is easily incremented for each face addition without being recalculated from scratch, and a final graph with all the new faces is easily recovered from the boundary information when there are no more updates.

```
force:: Tgraph -> Tgraph
force = recoverGraph . forceAll updatesBD . makeBoundary
makeBoundary :: Tgraph -> Boundary
recoverGraph :: Boundary -> Tgraph
forceAll :: (Boundary -> [Update]) -> Boundary -> Boundary
updatesBD:: Boundary -> [Update]
```

The recursive `(forceAll updatesBD)`

first uses `updatesBD`

to calculate a list of possible updates then selects a safe update, only doing an unsafe update if there are no safe ones. After doing an update it recurses, so it recalculates a new list of updates at each step (after each update). The saving that comes from using boundaries lies in efficient incremental changes to boundary information and, of course, in avoiding the need to consider internal faces.

In addition to `force`

we can easily define

```
wholeTiles:: Tgraph -> Tgraph
wholeTiles = recoverGraph . forceAll wholeTileUpdates . makeBoundary
```

which just uses the first forcing rule to make sure every half-tile has a matching other half.

We also have a version of `force`

which counts to a specific number of face additions.

`stepForce :: Int -> Tgraph -> Boundary`

This proved essential in uncovering problems of accumulated innaccuracy in calculating boundary positions (now fixed).

# Some Other Experiments

Below we describe results of some experiments using the tools introduced above. Specifically: emplacements, sub-Tgraphs, incorrect tilings, and composition choices.

# Emplacements

The finite number of rules used in forcing are based on local boundary vertex and edge information only. We may be able to improve on this by considering a composition and forcing at the next level up before decomposing and forcing again. This thus considers slightly broader local information. In fact we can iterate this process to all the higher levels of composition. Some graphs produce an empty graph when composed so we can regard those as maximal compositions. For example `composeG fool`

produces an empty graph.

The idea now is to take an arbitrary graph and apply `(composeG . force)`

repeatedly to find its maximally composed graph, then to `force`

the maximal graph before applying `(force . decomposeG)`

repeatedly back down to the starting level (so the same number of decompositions as compositions).

We call the function `emplace`

, and call the result the *emplacement* of the starting graph as it shows a region of influence around the starting graph.

With earlier versions of forcing when we had fewer rules, `emplace g`

often extended `force g`

for a Tgraph `g`

. This allowed the identification of some new rules. Since adding the new rules we have not yet found graphs with different results from `force`

and `emplace`

. [Although, the vertex labelling of the result will usually be different].

# Sub-Tgraphs

In figure 18 on the left we have a four times decomposed dart `dartD4`

followed by two sub-Tgraphs `brokenDart`

and `badlyBrokenDart`

which are constructed by removing faces from `dartD4`

(but retaining the connectedness condition and the no crossing boundaries condition). These all produce the same forced result (depicted middle row left in figure 15).

However, if we do compositions without forcing first we find `badlyBrokenDart`

fails because it produces a graph with crossing boundaries after 3 compositions. So `composeG`

on its own is not always safe, where *safe* means guaranteed to produce a valid `Tgraph`

from a valid correct `Tgraph`

.

In other experiments we tried `force`

on `Tgraph`

s with holes and on incomplete boundaries around a potential hole. For example, we have taken the boundary faces of a forced, 5 times decomposed dart, then removed a few more faces to make a gap (which is still a valid `Tgraph`

). This is shown at the top in figure 19. The result of forcing reconstructs the complete original forced graph. The bottom figure shows an intermediate stage after 2200 face additions. The gap cannot be closed off to make a hole as this would create a crossing boundary, but the channel does get filled and eventually closes the gap without creating a hole.

# Incorrect Tilings

When we say a Tgraph `g`

is a *correct graph* (respectively: *incorrect graph*), we mean `g`

represents a correct tiling (respectively: incorrect tiling). A simple example of an incorrect graph is a kite with a dart on each side (called a *mistake* by Penrose) shown on the left of figure 20.

```
*Main> mistake
Tgraph { vertices = [1,2,4,3,5,6,7,8]
, faces = [RK (1,2,4),LK (1,3,2),RD (3,1,5)
,LD (4,6,1),LD (3,5,7),RD (4,8,6)
]
}
```

If we try to `force`

(or `emplace`

) this graph it produces an error in construction which is detected by the test for conflicting edge types (a `phiEdge`

sharing with a non-`phiEdge`

).

```
*Main> force mistake
Tgraph {vertices = *** Exception: doUpdate:(incorrect tiling)
Conflicting new face RK (11,1,6)
with neighbouring faces
[RK (9,1,11),LK (9,5,1),RK (1,2,4),LK (1,3,2),RD (3,1,5),LD (4,6,1),RD (4,8,6)]
in boundary
Boundary ...
```

In figure 20 on the right, we see that after successfully constructing the two whole kites on the top dart short edges, there is an attempt to add an `RK`

on edge (1,6). The process finds an existing edge (1,11) in the correct direction for one of the new edges so tries to add the erroneous `RK (11,1,6)`

which fails a `noConflicts`

test.

So it is certainly true that incorrect graphs may fail on forcing, but forcing cannot create an incorrect graph from a correct graph.

If we apply `decomposeG`

to `mistake`

it produces another incorrect graph (which is similarly detected if we apply `force`

), but will nevertheless still compose back to `mistake`

if we do not try to force.

Interestingly, though, the incorrectness of a graph is not always preserved by `decomposeG`

. If we start with `mistake1`

which is `mistake`

with just two of the half darts (and also an incorrect tiling) we still get a similar failure on forcing, but `decomposeG mistake1`

is no longer incorrect. If we apply `composeG`

to the result or `force`

then `composeG`

the mistake is thrown away to leave just a kite (see figure 21). This is an example where `composeG`

is not a left inverse to either `decomposeG`

or `(force . decomposeG)`

.

# Composing with Choices

We know that unknowns indicate possible choices (although some choices may lead to incorrect graphs). As an experiment we introduce

`makeChoices :: Tgraph -> [Tgraph]`

which produces alternatives for the 2 choices of each of unknowns (prior to composing). This uses `forceLDB`

which forces an unknown to be a `largeDartBase`

by adding an appropriate joined half dart at the node, and `forceLKC`

which forces an unknown to be a `largeKiteCentre`

by adding a half dart and a whole kite at the node (making up the 3 pieces for a larger half kite).

Figure 22 illustrates the four choices for composing `fool`

this way. The top row has the four choices of `makeChoices fool`

(with the fool shown embeded in red in each case). The bottom row shows the result of applying `composeG`

to each choice.

In this case, all four compositions are correct tilings. The problem is that, in general, some of the choices may lead to incorrect tilings. More specifically, a choice of one unknown can determine what other unknowns have to become with constraints such as

- a and b have to be opposite choices
- a and b have to be the same choice
- a and b cannot both be largeKiteCentres
- a and b cannot both be largeDartBases

This analysis of constraints on unknowns is not trivial. The potential exponential results from choices suggests we should compose and force as much as possible and only consider unknowns of a maximal graph.

For calculating the emplacement of a graph, we first find the forced maximal graph before decomposing. We could also consider using `makeChoices`

at this top step when there are unknowns, i.e a version of `emplace`

which produces these alternative results (`emplaceChoices`

)

The result of `emplaceChoices`

is illustrated for `foolD`

in figure 23. The first force and composition is unique producing the `fool`

level at which point we get 4 alternatives each of which compose further as previously illustrated in figure 22. Each of these are forced, then decomposed and forced, decomposed and forced again back down to the starting level. In figure 23 `foolD`

is overlaid on the 4 alternative results. What they have in common is (as you might expect) `emplace foolD`

which equals `force foolD`

and is the graph shown on the right of figure 11.

# Future Work

I am collaborating with Stephen Huggett who suggested the use of graphs for exploring properties of the tilings. We now have some tools to experiment with but we would also like to complete some formalisation and proofs. For example, we do not know if `force g`

always produces the same result as `emplace g`

.

It would also be good to establish that `g`

is incorrect iff `force g`

fails.

We have other conjectures relating to subgraph ordering of `Tgraph`

s and Galois connections to explore.