Description of the order-5 square tiling of the hyperbolic plane as a graph

(Working with groups was too hard, so I decided to use a different approach, taking a leaf out of HyperRogue's book.)

We begin by constructing a spanning tree for the graph. It looks like this, except for being infinite:

Each path from the root to a vertex in the graph is described by an initial step North, East, South, or West, followed by a sequence of steps Forward, Left, or Right. In fact, all paths from the root can be described in this way, but the paths that correspond to to edges of this spanning tree satisfy two further conditions:

1. You can't take two consecutive steps Right.

2. You can't take two steps Left without a Right step somewhere in between.

   (Left, Left and Left, Forward, Left, and Left, Forward, Forward, Left and so on are all forbidden.)

In each quarter of the tree, the number of vertices at a given depth appears to be given by sequence A033303 in the OEIS.

To specify a vertex in the graph, we specify the path from the root to that vertex.

Of the four neighbors of a vertex, at least three are neighbors in the tree, and are easy to find. We just take the path specifying our vertex, and do one of:

• Erase the last step, or
• Append a Left, Forward, or Right step.

Sometimes, however, we get a non-tree edge in this way: this happens exactly when we take one of the forbidden steps above. In that case, we need to simplify the result to a path that is valid in the tree.

Let $\ell$ be the function that "turns a direction left", mapping North to West, West to South, South to East, East to North, Right to Forward, and Forward to Left; let $r$ be its inverse. (The values $\ell(\text{Left})$ and $r(\text{Right})$ are both undefined.) Then:

1. The forbidden ending "$\dots, x$, Right, Right" simplifies to the ending "$\dots, r(x)$, Left".
2. The forbidden ending "$\dots, x$, Left, Left" simplifies to the ending "$\dots, \ell(x)$, Right".
3. The forbidden ending $\dots, x$, Left, Forward, Left" simplifies to the ending $\dots, \ell(x)$, Right, Forward, Right".
4. In general, the forbidden ending "$\dots, x$, Left, Forward, ..., Forward, Left" simplifies to the ending "$\dots, \ell(x)$, Right, Forward, ..., Right, Forward, Right", with an equal number of Forward steps as before interleaved with Right steps.

You can represent this as the $\Delta(2,4,5)$ Von Dyck group.

In particular, you can generate the group by

• Rotate left 90 degrees ($L$)
• Rotate right 90 degrees ($R$)
• Move forward one cell, and then turn around ($F$)

Given a string of such symbols, we can simplify to a normal form with the following operations:

• Replace $L^2$ with $R^2$
• Remove $F^2$
• Replace $R^3$ with $L$
• Replace $(FL)^2F$ with $(RF)^2R$
• Replace $FLFR^2(FL)^2$ with $RF(RFR)^2F$
• Replace $(FLFR^2)^2$ with $RF(RFR)^2FL$

(generated with sagemath).

Any two representations of the same element in the Von Dyck group will normalize to the same result under these operations.

Finally, note that each element represents both a square, and a direction. Therefore, we will say that two elements represent the same square by ignoring $R$ and $L$ at the beginning of the string.

Two cells are adjacent if you can get from one to the other with zero to three $R$ operations and exactly one $F$ operation.