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

Question

What is a description of the graph representing the faces of the Order-5 square tiling. Alternatively, this can be seen as the graph of vertices of the its dual, the Order 4 pentagon tiling.

Preferably, it should be a description useful for use with a computer (all that is needed is a way to find the neighbors of any node). The reason why is got interested in using hyperbolic geometry in games, so as a short cut to all the calculus needed I decided I'd make a bunch of rooms corresponding to a tessellation of the hyperbolic plane (and approximate each room as Euclidean).

Also, these description should be discrete (i.e. not rely on real numbers (which would need to be approximated with floating numbers on a computer))?

Answer 1

(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.