Planar Locally Finite Cayley Graphs: Enumeration and Characterization

Title: Planar Locally Finite Cayley Graphs: Enumeration and Characterization

Research Question: How can we characterize and enumerate planar locally finite Cayley graphs, and what are their implications for decision problems?

Methodology: The researchers used a combination of graph theory, group theory, and combinatorial techniques to study planar locally finite Cayley graphs. They represented these graphs using labeling schemes and a local geometrical invariant called a type vector. They then developed algorithms to enumerate and describe these graphs, along with their presentations.

Results: The researchers were able to characterize the set of planar locally finite Cayley graphs and give a finite representation of these graphs using labeling schemes. They also developed algorithms to enumerate and describe all planar locally finite Cayley graphs of a given degree, along with one representative presentation. This led to algorithms solving the word problem for these graphs.

Implications: The results of this research have implications for decision problems on groups that are unsolvable in the general case. By providing a method to enumerate and describe planar locally finite Cayley graphs, the researchers have solved the problem of deciding whether a finite generated group possesses a presentation for which its Cayley graph is planar or not. This also extends Chaboud's work on planar Cayley graphs, providing a more general class of graphs and algorithms to build any finite ball of the graph.

In conclusion, the researchers have provided a comprehensive study of planar locally finite Cayley graphs, including their characterization, enumeration, and implications for decision problems. Their results have broadened our understanding of these graphs and their applications in group theory and combinatorics.

Link to Article: https://arxiv.org/abs/0309017v1 Authors: arXiv ID: 0309017v1