Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 39 (1998), No. 2, 269-282.

Connectivity and Planarity of Cayley Graphs

Carl Droms  Brigitte Servatius  Herman Servatius

Mathematics Department, James Madison University Harrisonburg, VA 22807

Department of Mathematical Sciences, Worcester Polytechnic Institute Worcester, MA 01610

Abstract. The question of which groups admit planar Cayley graphs goes back over 100 years, having been settled for finite groups by Maschke in 1896. Since that time, various authors have studied infinite planar Cayley graphs which satisfy additional special conditions. We consider the question of which groups possess any planar Cayley graphs at all by categorizing such graphs according to their connectivity. Like planarity, connectivity is a fundamental concept in graph theory. We show that having a Cayley graph which is less than three-connected has strong implications for the structure of the group. In the planar case, the decomposition imposed by low connectivity allows us to reduce the problem to the case where the Cayley graph is three-connected, where geometric techniques can be employed.

1. Introduction

Given a discrete group of isometries of the sphere, Euclidean plane or hyperbolic plane, one can construct a fundamental region whose translates tessellate the space. The dual of such a configuration is in fact a (modified) Cayley graph for the group. Figure 1 illustrates this construction for the group generated by the reflections in the sides of a spherical triangle with angles π/2, π/3 and π/5. Such a procedure gives rise to the familiar examples of Cayley graphs with a planar embedding. In 1896, Maschke [19] proved that the only finite groups which possess planar Cayley graphs are the discrete groups of isometries of the 2sphere. In other words, every finite planar Cayley graph arises from a construction such as in

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1998 Heldermann Verlag

Figure 1: Constructing a planar Cayley graph.

Figure 1 for the sphere. Zieschang, Vogt and Coldewey [29] enumerated the infinite discrete groups whose Cayley complexes are planar. Of course, requiring that the Cayley complex be planar is more restrictive than requiring merely that the Cayley graph be planar. Several authors have considered groups which possess planar Cayley graphs subject to various other restrictions [14, 18, 27]. We shall be concerned with groups which possess any planar Cayley graph whatsoever, groups we will call planar groups.

We note that many authors have studied the genus of a finite group, that is, the minimum genus of any surface into which a Cayley graph for the group can be embedded, see [8]. Levinson [12] showed that if an infinite Cayley graph is not planar, then it cannot be embedded in any surface of finite genus.

Planarity is a Markov property, so by a classical theorem of Adyan and Rabin [1, 20] there is no algorithm which decides, given a presentation, whether the group so presented is planar (see, for example, [17, Chapter IV]). The best one can hope for is a “catalogue” of presentations, each of which presents a planar group, and such that each planar group is represented, and we show that the first step toward such a catalogue is to classify the Cayley graphs by their connectivity.

If a group possesses a planar Cayley graph which is three-connected, then the Cayley graph may be embedded in the sphere in such a way that the left action on the Cayley graph is realized as a group of homeomorphisms of the sphere, so the group may be analyzed by geometric techniques. On the other hand, we will show that a group with any Cayley graph of connectivity less than three has a natural action on a tree. If the Cayley graph is also planar, the component groups of the resulting graph of groups themselves have planar Cayley graphs of higher connectivity. This method is not only useful for studying planar Cayley graphs, but forms an effective program for studying actions of groups on planar graphs, see [22, 23].

2. Preliminaries

Graphs. Recall that a directed graph consists of two sets, V (the set of vertices) and E (the set of edges), with two functions ι : E → V and τ : E → V. The vertex ι(e) is called the initial vertex of e, and τ(e) is called its terminal vertex.

Let G be a group with generating set X (all groups in this paper will be assumed to be finitely generated.) The (right) Cayley graph C(G, X) is the directed graph with vertex set G and edge set G × X, where the edge (g, x) has initial vertex g and terminal vertex gx. If x ∈ X has order two, we identify each pair of edges (g, x) and (gx, x) into a single “unoriented edge”. C(G, X) is sometimes referred to as a modified Cayley graph.

We shall be concerned only with the case where C(G, X) is reduced; that is, it has no loops and no multiple edges. This amounts to saying that 1 ∉ X, and if x ∈ X, then x^{−1} ∉ X, unless x has order two.

Connectivity. A separation of a connected graph Γ is a collection of vertices whose removal separates Γ into two or more connected components. A separation consisting of n vertices will be called an n-separation. Γ is said to be n-connected if it has no (n − 1)-separation; the largest n such that Γ is n-connected will be called the connectivity of Γ, denoted κ(Γ).

Suppose Γ can be written as a (possibly infinite) union

Γ = Γ_{1} ∪ Γ_{2} ∪ Γ_{3} ∪ ⋯

of subgraphs Γ_{i}. If for each n, Γ_{n} has exactly one vertex in common with Γ_{1} ∪ ⋯ ∪ Γ_{n−1}, then we call Γ the iterated one-point union of the Γ_{i}, and if Γ_{n} has exactly one edge and no other vertices in common with Γ_{1} ∪ ⋯ ∪ Γ_{n−1} for each n, we call Γ the iterated one-edge union of the Γ_{i}. We call either of these a proper decomposition if Γ_{n} is not a subgraph of Γ_{1} ∪ ⋯ ∪ Γ_{n−1} for any n. It is well known that a graph is one-separable if and only if it has a proper decomposition as iterated one-point union. (On the other hand, a two-separable graph need not be a one-edge union since the vertices in a separation need not be adjacent.)

If G is a group, we define the connectivity of G to be the minimum connectivity of all Cayley graphs of G.

Planarity. A graph is called planar if and only if it can be represented by a collection of points and arcs in the two-sphere S^{2} in such a way that two arcs do not intersect except possibly at their endpoints. If Γ is an embedding of some graph in S^{2}, then the connected components of S^{2} − \overline{Γ} are topological 2-disks called regions.

We shall require our embeddings to be tame in the following sense: first, if A is the set of accumulation points of vertices of Γ, then Γ ∩ A = ∅ and \overline{Γ} = Γ ∪ A. Second, we will require that the boundary of any region consist of a collection of disjoint paths of Γ, possibly together with some points of A.

Following Levinson [15], we say the elements of A are essential if the boundary of any region contains at most one of them. In this case, the boundary of any region is either a circuit of Γ or it is a two-way infinite path of Γ together with the common accumulation point of its two ends. A region whose boundary is a (finite) circuit of Γ will be called a finite region; the others will be called infinite regions. For example, Figure 2 shows the Cayley graph of the group Z × Z_{4} = ⟨a, b | a^{4} = 1, ab = ba⟩ embedded in the plane with two essential accumulation points. An infinite Cayley graph has one, two or infinitely many essential accumulation points [15]. Note that distinct ends of the group may correspond to the same essential accumulation point, as in the case of the free group of rank two whose Cayley graph (with respect to a free generating set) can be embedded in the sphere with a single accumulation point. On the other hand, the Cayley graph of the group Z_{2}^{3} ∗_{Z_{2}} Z_{2}^{3} with the obvious generating set is an infinite one-edge union of cubes (see Figure 3) which is hence planar, yet cannot be embedded with any finite number of accumulation points [6].

Figure 2: Part of a Cayley graph of Z × Z_{4}

Figure 3: Part of a Cayley graph of the group Z_{2}^{3} ∗_{Z_{2}} Z_{2}^{3}.

In general, if a graph Γ has a decomposition

Γ = Γ_{1} ∪ Γ_{2} ∪ Γ_{3} ∪ ⋯

as either iterated one-point union or iterated one-edge union, then Γ is planar if and only if each Γ_{i} is.

Groups acting on graphs. A graph of groups is a pair (X , G) where X is a directed graph with vertex set V and edge set E, and G is a function which assigns to each x ∈ V ∪E a group G(x), and two homomorphisms ι_{e} : G(e) → G(ι(e)) and τ_{e} : G(e) → G(τ(e)) for each e ∈ E. If x ∈ V, G(x) will be called a vertex group, and if e ∈ E, it will be called an edge group.

For each v ∈ V, let ⟨X_{v} | R_{v}⟩ be a presentation of G(v), where the X_{v} are taken to be pairwise disjoint. Then given a spanning tree T ⊆ X, we define the fundamental group π_{1}(X , T ) to have the following presentation:

Generators: - ∪_{v∈V}X_{v}
- {t_{e} | e ∈ E}, where the t_{e} are new symbols.
Relations: - ∪_{v∈V}R_{v}
- For each e ∈ E and for each g ∈ G(e), the relation
t_{e}^{−1}ι_{e}(g)t_{e} = τ_{e}(g).
- For each edge e of the spanning tree T , the relation
t_{e} = 1.

The generating set described above will be called the standard generating set for π_{1}(X , T ).

We recall the following facts about this construction (see [4, 5, 21]): first, if T′ is another spanning tree for X, then π_{1}(X , T′) ≃ π_{1}(X , T ). Thus, we write π_{1}(X).

Next, if all the homomorphisms ι_{e} and τ_{e} are injective, then so are the natural homomorphisms G(v) → π_{1}(X) for each v ∈ V. In this case, the graph of groups (X , G) is called faithful, and we may regard the vertex groups G(v) as subgroups of π_{1}(X).

Let T be the directed graph whose vertices are the left cosets of the subgroups G(v) (v ∈ V) in π_{1}(X), and whose edges are the left cosets of the subgroups G(e) (e ∈ E). The initial vertex of an edge gG(e) is the vertex gG(ι(e)) and its terminal vertex is gt_{e}G(τ(e)). T is a tree which is usually called the standard tree of the graph of groups (X , G).

Finally, let G be a group, and suppose that G acts on the left on a directed tree T. Let X = G\T. Choose a spanning tree T in X and a connected preimage T̃ of T in T; for any vertex or edge x of T , denote its preimage in T̃ by x̃. Also, for each edge e ∈ X − T , choose an edge ẽ ∈ T whose initial vertex lies in T̃.

For each vertex or edge x of X let G(x) be the stabilizer of x̃ under the G-action on T. If e ∈ T , then we may take the homomorphisms ι_{e} and τ_{e} to be the inclusions, since an element of G stabilizes an edge of T only if it stabilizes both its endpoints. If e ∈ Γ − T , choose an element g_{e} ∈ G so that g_{e}τ̃(e) = τ(ẽ). In this case, define ι_{e} to be inclusion, and τ_{e} to be conjugation by g_{e}. Then π_{1}(X , T ) is isomorphic to G, and the standard tree associated to X is T.

Let (X , G) be a graph of groups with G = π_{1}(X) and let X be the standard generating set for G. To each path P in the Cayley graph C(G, X) we associate a path P̃ in the standard tree T as follows: first, choose a vertex v_{0} of X. If P begins at g and ends at h in C, P̃ will be the unique reduced path in T from gG(v_{0}) to hG(v_{0}).

Now, it is straightforward to verify that if P̃ traverses an edge gG(e) for some edge e of X and some g ∈ G, then some vertex on the path P must belong to the coset gG(e) ⊆ G. (This is clear if P has length one, and if P_{1} ends at the beginning point of P_{2}, then any edge traversed by P̃_{1}.P_{2} is traversed by at least one of P̃_{1} or P̃_{2}.)

Since removing any edge from T separates T, we have:

Theorem 2.1. If G is the fundamental group of a faithful graph of groups, then in the Cayley graph of G with respect to the standard generating set, the elements of any edge group form a separation.

Planar groups. If a group G possesses a generating set X such that C(G, X) is planar, then we will say that G is planar, and that X is a planar generating set. We define the planar connectivity κ_{p}(G) of a planar group G to be the minimum connectivity of all its planar Cayley graphs. Since a Cayley graph is connected by definition, κ_{p}(G) ≥ 1 for every planar group G.

Theorem 2.2. (Babai [2]) Any subgroup of a planar group is planar.

In fact, suppose that Γ is a Cayley graph for G and that H is a subgroup of G. Then one can construct a Cayley graph for H as follows: choose a spanning tree T for the quotient H\Γ of the H-action on Γ, and contract each preimage of T in Γ to a point. Babai proves that H acts on the resulting graph Γ′. The action is free and transitive on the vertices of Γ′, and so Γ′ is a Cayley graph for H. Clearly Γ′ is planar if Γ is.

In fact, the following is an immediate corollary of his proof:

Corollary 2.3. If C(G, X) is planar and H is a subgroup of G, then H has a generating set Y with H ∩ X ⊆ Y such that C(H, Y) is planar.

3. Groups of low connectivity

In this section we investigate what can be concluded about the structure of a group assuming only that it possesses a Cayley graph of low connectivity.

One can describe the structure of a connected 1-separable graph Γ by forming its blockcutpoint tree B, see [24]. B has a vertex for each cutpoint of Γ, and one for each block, that is, for each maximal two-connected subgraph, of Γ. A vertex corresponding to a block is adjacent to one corresponding to a cutpoint if and only if the block contains the cutpoint. If a group acts on Γ then the action extends naturally to an action on B, and so the Bass-Serre theory can be used to study the structure of the group.

Theorem 3.1. A group G possesses a 1-separable Cayley graph if and only if G is either infinite cyclic or a non-trivial free product of infinite cyclic groups and groups of connectivity two or more.

Proof. Let C be a Cayley graph for G. If C has a cut vertex, then every vertex of C is a cutpoint. Let B be the block-cutpoint tree of C. G acts on the left on C, and therefore on B. No element of G stabilizes any vertex of C, so the G-stabilizer of any edge of B is also trivial, since an element of G can fix an edge of B if and only if it fixes both endpoints of the edge. G fixes no block of C either, since any such block would have to contain every vertex of C, contradicting the 1-separability of C.

Thus, G is the fundamental group of a graph of groups whose underlying graph is the quotient G\B, whose edge groups are all trivial and whose vertex groups are all proper subgroups of G. Therefore, G is either a non-trivial free product or it is infinite cyclic. Moreover, G can be written as the free product of freely indecomposable groups, and a freely indecomposable group is either infinite cyclic or has connectivity at least two.

The converse is an immediate consequence of Theorem 2.1. □

Example 3.2. Consider the group Z_{4} ∗ Z_{2} = ⟨a, b | a^{4} = b^{2} = 1⟩, whose modified Cayley graph is depicted in Figure 4, in which we see that the free product structure exhibited by the action on the block-cutpoint tree is already apparent in the Cayley graph. Note that the blocks are themselves Cayley graphs. □

Example 3.3. The Cayley graph of ⟨a, b | abab = 1⟩ is also 1-separable, see Figure 5, and the action on the block-cutpoint tree makes the free product decomposition apparent: the quotient of the block-cutpoint tree by the group action is a graph with two vertices joined by two edges. The stabilizers of the (solid) block vertices have order 2 and all the other stabilizers are trivial, and so by the Bass-Serre theory the group is isomorphic to Z ∗ Z_{2}. Note that the blocks are not themselves Cayley graphs in this case. □

Before discussing groups which possess two-separable Cayley graphs, we record some facts about graphs of connectivity two. The reader is referred to [24] for details about this in the case of finite graphs, and to [7] for infinite graphs.

Figure 4: The Cayley graph of Z_{4} ∗ Z_{2}, its block-cutpoint tree and quotient.

Figure 5: ⟨a, b | abab = 1⟩.

The block-cutpoint tree encodes how to construct a one-separable graph from twoconnected pieces using the operation of vertex union. There is an analogous description for two-separable graphs. In this case the pieces are three-blocks, which may be either threeconnected graphs, circuits, or n-links, that is, two vertices joined by n ≥ 3 parallel edges. The operation analogous to vertex union is called edge amalgamation, under which two threeblocks are joined together along an edge – called a virtual edge – which is then deleted. Since the virtual edges are deleted, the three-blocks need not be subgraphs of Γ. They are, however, homeomorphic to subgraphs of Γ, so Γ is planar if and only if all its three-blocks are, and in fact the graph obtained from Γ by adjoining any virtual edges is also planar in this case. As in the case of the block-cutpoint tree, each element of Aut(Γ) induces an automorphism of the three-block tree.

Lemma 3.4. Let G be a group which has a two-separable Cayley graph C = C(G, X) with respect to some generating set X. Then G = π_{1}(X) for some graph of groups (X , G), where |G(e)| ≤ 2 for each edge e of X.

Proof. Let B be the 3-block tree of C. Since G acts on C, it acts on B. As before, G is the fundamental group of the graph of groups (X , G), where X = G\B.

Now, since the stabilizer in G of any virtual edge of C has order one or two, and since each edge of B is incident to a vertex corresponding to a virtual edge of C, it follows that the stabilizer in G of any edge of B has order at most two. □

Lemma 3.5. If C has more than one three-block, then (X , G) is nontrivial; that is, G stabilizes no three-block of C and no virtual edge of C.

Proof. G acts transitively on the vertices of C, so if G stabilizes a virtual edge, then |G| = 2 and C can have only one three-block.

If G stabilizes a 3-block b of C, then b must contain all the vertices of C. Therefore, each 3-block other than b contains exactly two vertices, and is thus an n-link for some n. Since two n-links cannot be adjacent to one another, see [7], each 3-block other than b is adjacent only to b. Therefore, each three-block other than b is a link with one virtual edge and two or more “real” edges, which is impossible since C is reduced. □

A theorem of Linnell [16] says that if n is a positive integer, then any finitely-generated group has a maximal expression as the fundamental group of a graph of groups whose edge groups have order n or less; that is, one whose vertex groups cannot be so decomposed. This allows us to conclude:

Theorem 3.6. If κ(G) = 2 then either G is a finite cyclic or dihedral group, or it is the fundamental group of a graph of groups whose edge groups have order two or less and whose vertex groups have connectivity at least three.

Proof. Let C be a Cayley graph for G with connectivity two. If C has only one threeblock, then it is a finite polygon, and so G is either a finite cyclic or a finite dihedral group. Otherwise, it follows from Lemmas 3.4 and 3.5 that G has such a decomposition, and from Linnell’s theorem we may conclude that it has one whose vertex groups have connectivity at least three. □

Example 3.7. Figure 6 shows the Cayley graph of the group

⟨a, b, c | a^{2} = b^{2} = c^{2} = (ab)^{3} = (bc)^{2} = 1⟩

in which the stabilizers of the hexagon 3-blocks are conjugate to A=⟨a, b | a^{2} =b^{2} =(ab)^{3} =1⟩, the stabilizers of the quadrilateral 3-blocks are conjugate to C = ⟨b, c | b^{2} = c^{2} = (bc)^{2} = 1⟩, and the stabilizers of the virtual edges are conjugate to B = ⟨b | b^{2} = 1⟩, corresponding to the representation of the group as A ∗_{B} C. Note that the 3-blocks are all Cayley graphs. □

Example 3.8. The stabilizers of the virtual edges may also be trivial, as in the case of ⟨a, b | (ab^{2})^{2} = 1⟩, whose Cayley graph is drawn in Figure 7 in which the curved edges correspond to generator a and the straight edges correspond to generator b. Examining the 3-block tree reveals the isomorphism with the free product Z ∗ Z_{2}. □

Figure 6: A 2-connected Cayley graph.

Figure 7: A 2-connected Cayley graph.

4. Planar connectivity

4.1. Low Planar connectivity

We turn again to planar Cayley graphs.

Theorem 4.1. A group G has a 1-separable planar Cayley graph if and only if it is either infinite cyclic or a non-trivial free product of planar groups.

Proof. Choose a generating set X for G such that C(G, X) is planar and one-separable. If G is not infinite cyclic, then it is a non-trivial free product G_{1} ∗ G_{2}, and each G_{i} is planar, by Babai’s Theorem.

Conversely, suppose that G has such a decomposition. Choose a generating set X_{i} for each G_{i} so that the Cayley graphs C_{i} = C(G_{i}, X_{i}) are both planar, and let X = X_{1} ∪ X_{2}. Then it is straightforward to verify that C(G, X) is the iterated one-point union of subgraphs isomorphic to the C_{i}, and so it is planar and 1-separable. □

In fact, we can say a little more. Since any finitely generated group can be written as a free product of freely indecomposable groups, we have

Corollary 4.2. If G is planar with κ_{p}(G) = 1, then G is either infinite cyclic, or it is a free product of planar groups of planar connectivity two or more.

Finally, we record the following fact:

Proposition 4.3. If G has one Cayley graph which is 1-separable, and another which is planar, then κ_{p}(G) = 1.

Proof. This is clear if G is infinite cyclic. Otherwise, the first condition implies that G is a non-trivial free product, and the second condition and Babai’s theorem imply that the free factors are planar. As in the proof of Theorem 4.1, G has a planar, one-separable Cayley graph. □

Theorem 4.4. If G has planar connectivity 2, then either G is a finite cyclic or dihedral group, or it is the fundamental group of a graph of groups whose edge groups all have order two or less and whose vertex groups all have planar connectivity at least three. In the latter case, the vertex groups have planar generating sets which include the nontrivial elements of the incident edge groups.

Proof. If G has a 2-separable Cayley graph with only one three-block, then it is a finite polygon, and so G is a finite cyclic or dihedral groups. Otherwise, Theorem 3.4 guarantees that G has the given structure. Corollary 2.3 guarantees that the vertex groups are planar, and the statement about the generating sets of the vertex groups follows from the fact that a two-separable planar graph remains planar when the virtual edges are adjoined. □

It is conceivable that a planar group may have connectivity two but planar connectivity greater than two. However, if G = G_{1} ∗_{A} G_{2}, where A has order two, and if there are planar generating sets X_{1} and X_{2} for G_{1} and G_{2}, respectively, each of which contains the nontrivial element of A, then it is easy to see that C(G, X_{1} ∪ X_{2}) is an iterated one-edge union of subgraphs isomorphic to C_{1} and C_{2}, and so it has planar connectivity two.

In the case of an HNN extension G_{1} ∗_{A}, if G_{1} has a planar generating set X_{1} containing both the generator of A and its conjugate by the stable letter t of the HNN extension, then the Cayley graph of G with respect to the generating set X_{1} ∪ {t} is easily seen to be the iterated one-edge union of subgraphs isomorphic to C_{1} with quadrilaterals labeled atbt^{−1}, and so it is planar and has connectivity two in this case, as well.

4.2. Higher planar connectivity

We begin with a theorem about three-connected planar graphs:

Theorem 4.5. Let Γ be a three-connected planar graph, and let c be a simple circuit of Γ. If c bounds a disk in some planar embedding of Γ, then it does so in every such embedding.

Proof. This is an immediate consequence of Whitney’s theorem on the unique embeddability of planar three-connected graphs (see [26] for a proof in the finite case, and [11] for the infinite case.) □

Thus we may say unambiguously that a particular circuit of a three-connected planar Γ “bounds a disk”.

Corollary 4.6. If c bounds a disk, then so does its image under any automorphism of Γ. In particular, if Γ is a Cayley graph, and if w is the boundary label of a circuit which bounds a disk, then every circuit with label w bounds a disk.

Let G be an infinite group with generating set X, let Γ be a tame embedding of the Cayley graph of G in S^{2}, and let A be the set of accumulation points of vertices of Γ. Suppose also that Γ is three-connected and that A is essential.

If |A| = 1, then it is easy to see that the union of Γ with the disks bounded by circuits of Γ is in fact a (planar) Cayley complex for G, and so G is either a “planar discontinuous group” (studied by Zieschang, Vogt and Coldewey [29]) or a “non-Euclidean crystallographic group” studied by MacBeath [18] (see also [17, Chapter 3]). We will refer to such groups collectively as “plane groups”.

If |A| = 2, then Γ is a so-called “cylindric embedding” of the Cayley graph of G, which has been studied by Levinson. (Note that although there is an error in this paper [28], the results are correct if the Cayley graph is also assumed to be three-connected.) In particular, G is a one-relator quotient of a plane group.

If |A| > 2, then A is in fact infinite [15]. Let U be the universal cover of S^{2} − A (which exists since A is closed) and let Γ̃ be the preimage of Γ under the covering map p : U → S^{2}−A. Let D be the subset of S^{2} consisting of Γ and all the finite regions. Then it is easy to see that D has the structure of a connected 2-complex whose 1-skeleton is Γ. Furthermore, the boundary of each infinite region consists of a two-way infinite path of Γ and one accumulation point, and so S^{2} − A contracts onto D.

Proposition 4.7. Γ̃ is connected.

Proof. Since S^{2} − A contracts onto D, any path in S^{2} − A whose endpoints lie in Γ is homotopic to one lying in Γ. Therefore, the same is true of any path in U joining two points of Γ̃; in particular, Γ̃ is connected. □

Let S be the set of labels of circuits in Γ which bound (finite) regions, and let G̃ be the group with presentation ⟨X | S⟩.

Theorem 4.8. Γ̃ is the Cayley graph of G̃ relative to the given generating set.

Proof. It is clear that any path in Γ̃ whose label belongs to S is a loop, and so it will suffice to prove that the label of any loop in Γ̃ can be written as a product of conjugates of elements of S. Let ℓ be such a loop. Then ℓ is contractible in U. But this implies that its image p(ℓ)

– which has the same label as ℓ – is contractible in S^{2} − A. But since S^{2} − A contracts onto D, p(ℓ) is contractible in D, which implies that its label is a product of conjugates of region boundaries. □

Now let N be the group of covering transformations for the covering p : U → S^{2} − A.

Theorem 4.9. N is isomorphic to K = ker(G̃ → G).

Proof. Let α ∈ N, and let ℓ be the label of the path in Γ̃ from the vertex “1” to α(1). Since p(1) = p(α(1)) in Γ ⊆ S^{2} − A, it is clear that the word ℓ represents an element of G̃ which maps to 1 ∈ G.

Conversely, if W is a word representing an element of K, then the path in Γ with label W and beginning at 1 is a loop, ℓ. But then there is a unique covering transformation mapping 1 ∈ Γ̃ to the other endpoint of the preimage ℓ̃ of ℓ in U.

Finally, it is easy to check that these correspondences are indeed homomorphisms. □

Now, one may identify an infinite plane group with a discrete group of motions of either the Euclidean plane R^{2} or the hyperbolic plane H^{2}, and so N would be a discrete group acting on the same space and having a planar quotient. Thus, one approach to the problem of producing a catalogue of planar groups would be to try to catalogue the groups of motions of R^{2} and H^{2} which have planar quotient spaces. (Along these lines, one knows a condition on such a group which guarantees that its quotient is orientable [10].)

5. Geometrization

Given a planar Cayley graph, is there always a nice picture for it? In other words, is there always an equivariant embedding of the Cayley graph in a convenient geometric surface: the sphere, Euclidean plane, hyperbolic plane, infinite cylinder, or infinitely punctured hyperbolic plane, so that the action of the group on the Cayley graph is realized by isometries of the space? We know that this always works for 3-connected planar Cayley graphs, as well as for 1-separable Cayley graphs all of whose blocks are 3-connected. For 2-connected planar Cayley graphs, however, there need not exist an equivariant embedding.

Theorem 5.1. There exists Cayley graphs which are planar and 2-connected, but which have no embedding in the sphere for which the natural left action on the Cayley graph is realized by homeomorphisms.

In Figure 8 we see the construction of a planar Cayley graph for the free product with

Figure 8:

Z_{2}-amalgamation of D_{3} and Z_{3} × Z_{2}. The Cayley graphs of both factors are triangular prisms, pictured on the left in Figure 8 with the orientations of the edges of the triangles indicated, and the spokes of the prism, representing involutory edges, indicated by 2-gonal cells. The Cayley graph of the amalgamation embeds in the sphere, with the upper and lower hemispheres shown. Since the Z_{2} action in Z_{3} × Z_{2} on the prism is by reflection, while the Z_{2} action in D_{3} on the prism is by rotation, amalgamating these incompatible actions yields a planar Cayley graph which has no equivariant embedding.

References

[1] Adyan, S. I.: On algorithmic problems in effectively complete classes of groups. Dokl. Akad. Nauk SSSR 123 (1958), 13–16.

[2] Babai, L.: Some applications of graph contractions. J. Graph Theory 1 (1977), 125–130.

[3] Cohen, D. E.: Groups with free subgroups of finite index. In: “Conference on Group Theory, University of Wisconsin–Parkside 1972”, Lecture Notes in Mathematics 319, Springer-Verlag, Berlin 1973.

[4] Dicks, W.: Groups, Trees and Projective Modules. Lecture Notes in Mathematics 790, Springer-Verlag, Berlin 1980.

[5] Dicks, W.; Dunwoody, M. J.: Groups Acting on Graphs. Cambridge Studies in Advanced Mathematics 17, Cambridge University Press, Cambridge 1989.

[6] Droms, C.; Servatius, H.: The Cayley graphs of Coxeter and Artin groups. Proc. Amer. Math. Soc. 118 (1993), 693–698.

[7] Droms, C.; Servatius, B.; Servatius, H.: The structure of locally finite 2-connected graphs. Electronic Journal of Combinatorics 2 (1995), #R17.

[8] Gross, J.; Tucker, T.: Topological Graph Theory. John Wiley & Sons, New York 1987.

[9] Harary, F.: Graph Theory. Addison-Wesley, Reading, MA, 1969.

[10] Hoare, A. H. M.; Singerman, D.: The orientability of subgroups of plane groups. In: “Groups–St. Andrews 1981”, London Math. Soc. Lecture Note Ser. 71, Cambridge Univ. Press, Cambridge-New York 1982, 221–227.

[11] Imrich, W.: On Whitney’s theorem on the unique embeddability of 3-connected planar graphs. Czechoslovak Symposium on Graph Theory (2nd, 1974, Prague, Czechoslovakia), Recent advances in graph theory: proceedings of the Symposium held in Prague, June 1974 / scientific editor, Miroslav Fiedler; Czechoslovak Academy of Sciences, Praha 1975.

[12] Levinson, H.: On the genera of graphs of group presentations. Ann. New York Acad. Sci. 175 (1970), 277–284.

[13] Levinson, H.: On the genera of graphs of group presentations III. J. Combinatorial Theory Ser. B 13 (1972), 298–302.

[14] Levinson H.; Hevia, H.: Cylindric Embeddings of P.S. and W.P.S. Planar Cayley Diagrams. Congr. Numer. 66 (1988), 173–180.

[15] Levinson, H.: Planar Cayley diagrams. Congr. Numer. 36 (1982), 207–215.

[16] Linnell, P. A.: On accessibility of groups. J. Pure Appl. Algebra 30 (1983), 39–46.

[17] Lyndon, R.; Schupp, P.: Combinatorial Group Theory. Ergebnisse der Mathematik und ihrer Grenzgebiete 89, Springer-Verlag, Berlin 1977.

[18] MacBeath, A.: The classification of non-Euclidean plane crystallographic groups. Canad. J. Math. 6 (1967), 1192–1205.

[19] Maschke, H.: The representation of finite groups, Amer. J. Math. 18 (1896), 156–194.

[20] Rabin, M. O.: Recursive unsolvability of group theoretic problems. Ann. of Math. 67 (1958), 172–174.

[21] Serre, J.-P.: Trees. Springer-Verlag, Berlin 1980.

[22] Servatius B.; Servatius, H.: The 24 symmetry pairings of self-dual maps on the sphere. Discrete Math. 140 (1995), 167–180.

[23] Servatius B.; Servatius, H.: Self-dual graphs. Discrete Math. 149 (1996), 223–232.

[24] Tutte, W.: Graph Theory. Encyclopedia of Mathematics and its Applications 21, Cambridge University Press, Cambridge 1984.

[25] White, A. T.: On the genus of a group. Trans. Amer. Math. Soc. 173 (1972), 203–214.

[26] Whitney, H.: Congruent graphs and the connectivity of graphs. Amer. J. Math. 54 (1932), 150–168.

[27] Wilkie, H.: On non-Euclidean crystallographic groups. Math. Z. 91 (1966), 87–102.

[28] Witte, D. R.: Review of “Cylindric embeddings of P.S. and W.P.S. planar Cayley diagrams”, Mathematical Reviews 90h:05044, 1990.

[29] Zieschang, H.; Vogt, E.; Coldewey, H.-D.: Flächen und ebene diskontinuierliche Gruppen. Springer-Verlag, Berlin Heidelberg New York 1970.

Received April 24, 1997