The planar Cayley graphs are effectively enumerable. I: Consistently planar graphs

DOI10.1007/S00493-019-3763-3MaRDI QIDQ2288356zbMATH OpenOpenAlexWikidataFDO

Authors Matthias Hamann, Agelos Georgakopoulos

Publication date 17 January 2020

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.03361, http://wrap.warwick.ac.uk/110733/2/WRAP-planar-Cayley-graphs-effectively-enumerable-I-Georgakopoulos-2018.pdf

zbMATH Keywords

effective enumerationplanar finitely generated Cayley graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Generators, relations, and presentations of groups (20F05) Geometric group theory (20F65)

Abstract: We obtain an effective enumeration of the family of finitely generated groups admitting a faithful, properly discontinuous action on some 2-manifold contained in the sphere. This is achieved by introducing a type of group presentation capturing exactly these groups. Extending this in a companion paper, we find group presentations capturing the planar finitely generated Cayley graphs. Thus we obtain an effective enumeration of these Cayley graphs, yielding in particular an affirmative answer to a question of Droms et al.

Review text

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.

Recommendations

• The planar Cayley graphs are effectively enumerable. II
• Enumerating planar locally finite Cayley graphs.
• About planar cayley graphs
• Cayley graphs having nice enumerations
• Connectivity and planarity of Cayley graphs
• PLANAR CAYLEY GRAPHS WITH REGULAR DUAL
• The enumeration of planar graphs via Wick's theorem
• The planar cubic Cayley graphs
• The planar cubic Cayley graphs of connectivity 2
• On the planarity of cyclic graphs

Cited in

(12)

• Connectivity and planarity of Cayley graphs
• The planar cubic Cayley graphs of connectivity 2
• Characterising planar Cayley graphs and Cayley complexes in terms of group presentations
• Enumerating planar locally finite Cayley graphs.
• The planar Cayley graphs are effectively enumerable. II
• Researches of semigroups with planar Cayley graphs: results and problems
• On planar Cayley graphs and Kleinian groups
• THE RANKS OF PLANARITY FOR VARIETIES OF COMMUTATIVE SEMIGROUPS
• Infinite-ended groups with planar Cayley graphs
• On the Cayley graph of a generic finitely presented group
• Periodic colorings and orientations in infinite graphs
• A note on the structure of locally finite planar quasi-transitive graphs

This page was built for publication: The planar Cayley graphs are effectively enumerable. I: Consistently planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2288356)