Enumerating planar locally finite Cayley graphs. (Q2571720)

Cayley graphs are represented in the paper under review by finite state automata called labelling schemes together with a local geometric invariant called a type vector. It is shown that there exists a bijection between this representation and the class of locally finite planar Cayley graphs. The main result is an enumeration theorem, namely that for \(n\geq 2\) all planar locally finite Cayley graphs having internal degree \(n\) can be effectively enumerated, along with one representative presentation. For each Cayley graph belonging to this class there exists an algorithm able to build any finite ball of the graph, which leads to algorithms solving the word problem. Complete lists of locally finite Cayley graphs of degree 3 and 4, together with presentation, type vector, and figure for each class, are given in the appendix.