The planar Cayley graphs are effectively enumerable. I: Consistently planar graphs (Q2288356)

Planar discontinuous groups correspond to Cayley graphs that can be embedded into the plane without accumulation points of vertices. \par The Cayley complex corresponding to a group presentation \( \mathcal{P} = \langle S \vert R \rangle \) is the \(2\)-complex obtained from the Cayley graph for \( \mathcal{P} \) by glueing \(2\)-cells along the closed walks induced by the relators in \(R\), and planar discontinuous groups also coincide with groups admitting a planar modified Cayley complex.\par The authors extend the correspondence between planar Cayley complexes and accumulation-free planar Cayley graphs by relaxing the notion of planarity of a Cayley complex in such a way that it corresponds exactly to its Cayley graph being planar. The related new notion of `almost planarity' of a Cayley complex can then be recognised algorithmically, which consequently allows for effective enumeration of the family of finitely generated groups admitting a faithful, properly discontinuous action on some \(2\)-manifold contained in the sphere. An effective enumeration of an infinite set is understood as a computer program that outputs elements of this set and nothing else, with every element in the output after some finite time (with repetitions allowed). \par This is the first paper of a two paper series devoted to the topic of effective enumeration of planar finitely generated Cayley graphs.