×

zbMATH — the first resource for mathematics

Characterising planar Cayley graphs and Cayley complexes in terms of group presentations. (English) Zbl 1284.05123
Summary: We prove that a Cayley graph can be embedded in the Euclidean plane without accumulation points of vertices if and only if it is the 1-skeleton of a Cayley complex that can be embedded in the plane after removing redundant simplices. We also give a characterisation of these Cayley graphs in term of group presentations, and deduce that they can be effectively enumerated.

MSC:
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Bogopolski, O., Introduction to group theory, (2008), EMS Zurich, Switzerland
[2] Cui, Q.; Wang, J.; Yu, X., Hamilton circles in infinite planar graphs, J. Combin. Theory Ser. B, 99, 1, 110-138, (2009) · Zbl 1193.05117
[3] Diestel, R., Graph theory, (2005), Springer-Verlag · Zbl 1074.05001
[4] Droms, C., Infinite-ended groups with planar Cayley graphs, J. Group Theory, 9, 4, 487-496, (2006) · Zbl 1099.20017
[5] Droms, C.; Servatius, B.; Servatius, H., Connectivity and planarity of Cayley graphs, Beiträge Algebra Geom., 39, 2, 269-282, (1998) · Zbl 0917.05036
[6] M.J. Dunwoody, Planar graphs and covers. Preprint. · Zbl 1021.74011
[7] A. Georgakopoulos, The planar cubic Cayley graphs of connectivity 2, 2010. Preprint. · Zbl 1365.05123
[8] A. Georgakopoulos, The planar cubic Cayley graphs, 2011. Preprint. · Zbl 1353.05002
[9] Halin, R., Zur häufungspunktfreien darstellung abzählbarer graphen in der ebene, Arch. Math., 17, 239-243, (1966) · Zbl 0141.40904
[10] Hatcher, A., Algebraic topology, (2002), Cambrigde University Press · Zbl 1044.55001
[11] W. Imrich, On Whitney’s theorem on the unique embeddability of 3-connected planar graphs, in: Recent Adv. Graph Theory, Proc. Symp. Prague 1974, 1975, pp. 303-306.
[12] Kavitha, T.; Liebchen, C.; Mehlhorn, K.; Michail, D.; Rizzi, R.; Ueckerdt, T.; Zweig, K., Cycle bases in graphs characterization, algorithms, complexity, and applications, Comput. Sci. Rev., 3, 4, 199-243, (2009) · Zbl 1301.05195
[13] Keller, M., Curvature, geometry and spectral properties of planar graphs, Discrete Comput. Geom., 46, 500-525, (2011) · Zbl 1228.05129
[14] Kozma, G., Percolation, perimetry, planarity, Rev. Mat. Iberoam., 23, 2, 671-676, (2007) · Zbl 1131.60087
[15] Macbeath, A. M., The classification of non-Euclidean plane crystallographic groups, Canad. J. Math., 19, 1192-1205, (1967) · Zbl 0183.03402
[16] Thomassen, C., Planarity and duality of finite and infinite graphs, J. Combin. Theory Ser. B, 29, 2, 244-271, (1980) · Zbl 0441.05023
[17] Whitney, H., Congruent graphs and the connectivity of graphs, Amer. J. Math., 54, 1, 150-168, (1932) · JFM 58.0609.01
[18] Wilkie, H. C., On non-Euclidean crystallographic groups, Math. Z., 91, 87-102, (1965) · Zbl 0166.02602
[19] Zieschang, H.; Vogt, E.; Coldewey, H.-D., (Surfaces and Planar Discontinuous Groups, Lecture Notes in Mathematics, vol. 835, (1980), Springer-Verlag), Revised and Expanded transl. from the German by J. Stillwell
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.