Computing JSJ decompositions of hyperbolic
groups

arXiv:1611.00652v4 [math.GT] 28 Mar 2018

Benjamin Barrett
March 29, 2018
Abstract
We present an algorithm that computes Bowditch’s canonical JSJ decomposition of a given one-ended hyperbolic group over its virtually cyclic
subgroups. The algorithm works by identifying topological features in the
boundary of the group. As a corollary we also show how to compute the
JSJ decomposition of such a group over its virtually cyclic subgroups with
infinite centre. We also give a new algorithm that determines whether or
not a given one-ended hyperbolic group is virtually fuchsian. Our approach uses only the geometry of large balls in the Cayley graph and
avoids Makanin’s algorithm.

0

Introduction

When studying a group it is natural and often useful to try to cut it into
simpler pieces by means of amalgamated free products and HNN extensions
over particularly simple subgroups. Sometimes this can be done in a canonical
way analogous to the characteristic submanifold decomposition of Jaco, Shalen
and Johannson [24, 25], in which the family of embedded tori along which the
3-manifold is cut is unique up to isotopy. Such JSJ decompositions were introduced to group theory by Sela [32] to answer questions about rigidity and
the isomorphism problem for torsion-free hyperbolic groups. In [8] Bowditch
developed a related type of decomposition for hyperbolic groups possibly with
torsion. This decomposition is built from the structure of local cut points in
the boundary of the group and is therefore an automorphism invariant of the
group; this property of the Bowditch JSJ was used in Levitt’s work [27] on
outer automorphism groups of one-ended hyperbolic groups. For more general
constructions of JSJ decompositions of groups see [30, 16, 18, 23].
The above results describe and prove the existence of various types of JSJ
decompositions but do not give an algorithm to construct them. Gerasimov [20]
proved that there exists an algorithm that determines whether or not the Gromov boundary of a given hyperbolic group is connected. This algorithm is
unpublished; see also [14]. The connectedness of the boundary is determined by
the so-called double-dagger condition of Bestvina and Mess [2]; it is this condition that Gerasimov showed to be computable. Equipped with this algorithm
and Stallings’s theorem on ends of groups it is not difficult to compute a maximal decomposition of a given hyperbolic group over its finite subgroups. With
Gerasimov’s result in hand, we may restrict to the case of one-ended hyperbolic
1

groups and consider the computability of Bowditch’s JSJ decomposition over
virtually cyclic subgroups.
In this paper we present an algorithm that computes Bowditch’s decomposition. Like Gerasimov’s algorithm, our approach uses the geometry of large
balls in the Cayley graph. This is in contrast to existing algorithms computing
JSJ decompositions over restricted families of virtually cyclic subgroups, most
of which rely on Makanin’s algorithm for solving equations in free groups.
In [15] Dahmani and Guirardel show that a canonical decomposition of a oneended hyperbolic group over a particular family of virtually cyclic subgroups is
computable; the family in question is the set of virtually cyclic subgroups with
infinite centre that are maximal for inclusion among such subgroups. Crucial
to this method is an algorithm that determines whether or not the outer automorphism group of such a group is infinite. If a group admits such a splitting
then that splitting gives rise to an infinite set of distinct elements of the outer
automorphism group that are analogous to Dehn twists in the mapping class
group of a surface. The converse of this statement is a theorem of Paulin [29]
that is refined by Dahmani and Guirardel.
Dahmani and Guirardel comment that it is not known whether or not
Bowditch’s JSJ decomposition is computable. Their approach is not suitable to
this problem: only central elements of the edge groups in a splitting contribute
Dehn twists to the automorphism group, so it is quite possible for a group to
admit a splitting over an infinite dihedral group, say, while having only a finite
outer automorphism group; in this case the decomposition computed by Dahmani and Guirardel is trivial while Bowditch’s JSJ decomposition is not. For
examples of hyperbolic groups exhibiting this property see [28].
In the absence of torsion, the JSJ decomposition of a hyperbolic group over
its cyclic subgroups was shown to be computable by Dahmani and Touikan
in [12]. Their result is based on Touikan’s algorithm [33], which determines
whether or not a given one-ended hyperbolic group without 2-torsion splits
acylindrically. Touikan’s methods are based on application of the Rips machine.
The existence of a splitting of a one-ended hyperbolic group over a virtually
cyclic subgroup is reflected in the existence of certain topological features in its
Gromov boundary by results of Bowditch [8, 4, 3]; in this paper we show that
these topological features can be detected algorithmically.
Theorem 0.1. There is an algorithm that takes as input a presentation for
a one-ended hyperbolic group and returns the graph of groups associated to the
three following JSJ decompositions:
1. A JSJ decomposition over virtually cyclic subgroups of Γ, which we shall
call a VC-JSJ. This decomposition can be taken to be Bowditch’s canonical
decomposition.
2. A JSJ decomposition over virtually cyclic subgroups of Γ with infinite centre, which we shall call a Z-JSJ.
3. A decomposition over maximal virtually cyclic subgroups of Γ with infinite
centre that is universally elliptic over (not necessarily maximal) virtually
cyclic subgroups of Γ and is maximal for domination in the class of such
decompositions. We shall call this a Zmax -JSJ.

2

The main content of Theorem 0.1 is the computability of the VC-JSJ; it is
shown in [15] to be closely related to the Z-JSJ and Zmax -JSJ and can converted
into either algorithmically. The Zmax -JSJ is the decomposition shown to be
computable by Dahmani and Guirardel [15].
The Z-JSJ also plays a result in Dahmani and Guirardel’s work, although
they comment that their methods cannot compute this decomposition, since
such a decomposition does not necessarily give rise to infinitely many distinct
outer automorphisms of the group. For example, let Γ be a rigid hyperbolic
group (such as the fundamental group of a closed hyperbolic 3-manifold) and
let g be an element of Γ that is not a proper power. Let k > 1 and consider the
group Γ0 = Γ ∗g=tk hti obtained by adjoining a kth root of g to Γ. In this case
the Zmax decomposition computed by Dahmani and Guirardel is trivial while
the JSJ decomposition over virtually cyclic subgroups with infinite centre is not.
Central to the algorithm of Theorem 0.1 is an algorithm that determines
whether or not a given hyperbolic group with a (possibly empty) finite collection of virtually cyclic subgroups admits a proper splitting as an amalgamated
product or HNN extension over a virtually cyclic subgroup, relative to that collection of subgroups. Recall that a cut pair in a connected topological space
S is a pair of points p and q such that S − {p, q} is disconnected. It is shown
in [8] that in the absolute case (that is, if the collection of subgroups is empty),
a one-ended hyperbolic group admits such a splitting if and only if its Gromov
boundary contains a cut pair, at least as long as its boundary is not homeomorphic to a circle. In the case of interest here we obtain a relative version of
this statement by replacing the Gromov boundary with the Bowditch boundary of the group relative to the given family of subgroups. Unlike the Gromov
boundary, the Bowditch boundary might contain a cut point, in which case the
group admits a relative splitting. This is the peripheral splitting in the sense
of Bowditch [3]. In the absence of a cut point the existence of a relative splitting is determined by the existence of a cut pair, as in the absolute case. It is
the presence of these topological features of the boundary that we show to be
computable.
To detect the presence of a cut pair in the Bowditch boundary of a hyperbolic
group relative to a given family of subgroups we first show that the connectivity
of the complement of a pair of points in the boundary is equivalent to the
connectivity of a thickened cylinder around a geodesic connecting that pair of
points in the cusped space defined in [22]. Then, supposing that there is a
cut pair in the boundary, we use a pumping lemma argument to show that the
geodesic γ connecting the points in a cut pair may be assumed to be periodic
and with bounded period: we take a short subsegment γ|[a,b] of that geodesic
such that both the geodesic and the components of the thickened cylinder are
identical in small neighbourhoods of a and b and form a new (local) geodesic that
also connects the two points in a (possibly different) cut pair by concatenating
infinitely many copies of γ|[a,b] . A similar method is used in [10] to control
cut pairs in the decomposition space of a line pattern in a free group. This is
sufficient to detect a cut pair: the existence of such a periodic geodesic can be
detected in finite time by searching a large finite ball in the Cayley graph.
A maximal splitting is obtained from a JSJ decomposition by refining at
the flexible vertices. Conversely, to obtain a JSJ decomposition we must decide which edges of the maximal splitting should be collapsed to reassemble the
flexible vertices in the JSJ decomposition. In Bowditch’s JSJ decomposition
3

the stabilisers of flexible vertex groups are the maximal hanging fuchsian subgroups. These are those subgroups that occur as a vertex stabiliser in some
splitting such that the Bowditch boundary of the subgroup relative the stabilisers of the incident edges is homeomorphic to a circle. Therefore we prove the
following theorem, which is interesting in its own right, and does not seem to
appear in the literature. Recall that the Convergence Group Theorem of Tukia,
Casson, Jungreis and Gabai [34, 11, 19] implies that the Gromov boundary of
a hyperbolic group is homeomorphic to a circle if and only if the group surjects
with finite kernel onto the fundamental group of a compact hyperbolic orbifold.
Theorem 0.2. There is an algorithm that takes as input a hyperbolic group Γ
and a (possibly empty) collection of virtually cyclic subgroups H and returns an
answer to the question “is ∂(Γ, H) homeomorphic to S 1 ?”
The algorithm of Theorem 0.2 is similar to the algorithm that detects the
presence of a cut pair in the Bowditch boundary: it follows from a result in
point-set topology that the boundary is homeomorphic to a circle if and only if
every pair of points in the boundary is a cut pair. We show that if there is a
non-cut pair in the Bowditch boundary then there is a non-cut pair connected
in the cusped space by a local geodesic with bounded period.
In section 1 we first review the definition of the cusped space and the
Bowditch boundary. We then recall some important properties: the computability of the hyperbolicity constant of the cusped space, the existence of a visual
metric on the Bowditch boundary, and most importantly the so-called doubledagger condition, which will be vital in linking the connectivity of the boundary
to that of subsets of the cusped space. We then define a thickened cylinder
around a geodesic in the cusped space and show that its connectivity determines the connectivity of the complement of the limit set of that geodesic in
the boundary.
Section 2 contains the main technical results of the paper we describe the
algorithms that determine whether or not the Bowditch boundary of a hyperbolic group contains the three topological features of interest to us: cut points,
cut pairs and non-cut pairs.
In section 3 we deal with the special case of a group with circular Bowditch
boundary. We first recall some results that reduce the problem of determining
whether or not such a group admits a proper splitting relative to its given
virtually cyclic subgroups to the case in which the group is the fundamental
group of a compact two-dimensional hyperbolic orbifold and the given subgroups
are precisely conjugacy class representatives of the fundamental groups of the
boundary components of that orbifold. In [23] a complete list of such orbifolds
that do not admit such a splitting is described; we use this to complete this
special case.
In section 4 we first record the general definition of a JSJ decomposition and
a description of Bowditch’s canonical JSJ decomposition over virtually cyclic
subgroups. We then recall the theorem of [8] that links the topology of the
Gromov boundary of a hyperbolic group to the existence of a proper splitting
of that group and extend it to a relative version. We then show how to use
the algorithms described so far to compute a maximal splitting of a one-ended
hyperbolic group over virtually cyclic subgroups.
In section 5 we complete the proof of Theorem 0.1 by describing the processes
that convert a maximal splitting of a one-ended hyperbolic group over virtually
4

cyclic subgroups into its VC-JSJ, Z-JSJ and Zmax -JSJ.
It seems plausible that the techniques of this paper might extend to the
problem of detecting the presence of splittings of relatively hyperbolic groups
with parabolic subgroups in some restricted class. In particular, it is natural to
try to solve this problem for groups that are hyperbolic relative to finitely generated virtually nilpotent subgroups. Such groups arise as fundamental groups
of complete finite volume Riemannian manifolds with pinched negative sectional
curvature. However, it is of fundamental importance to the argument presented
in this paper that the cusped space associated to the group satisfies Bestvina
and Mess’s double-dagger condition, and we do not know under what circumstances this condition holds for virtually nilpotent parabolic subgroups. In [14]
it is established that the double-dagger condition holds if the parabolic subgroups are abelian, so it seems likely that the methods of this paper could be
extended to the case of toral relatively hyperbolic groups. (A group is toral relatively hyperbolic if it is torsion free and hyperbolic relative to a finite collection
of abelian subgroups.) However, the JSJ decomposition of a toral relatively
hyperbolic group is shown to be computable in [12], so we do not introduce
additional technical complexity by trying to give a new proof of this result here.

Acknowledgements
I thank my supervisor Henry Wilton for suggesting this problem and for his
guidance towards its solution. I am also grateful to the anonymous reviewer for
pointing out several problems with the clarity and accuracy of the earlier draft.

1

The cusped space and cut pairs

1.1

The cusped space and the boundary

In this section we recall some technical results about the geometry of relatively
hyperbolic groups. Fix a group Γ with a finite generating set S and a finite
collection H of subgroups of Γ such that H ∩ S is a generating set for H for
each H in H. For now we may allow the groups in H to be arbitrary, although
in our application they will be virtually cyclic.
In [22] the cusped space X associated to the triple (Γ, S, H) is defined; we
recall the definition here. See [22] for more details and properties of the cusped
space. We use only the 1-skeleton of the cusped space so we omit the 2-cells
from the definition.
b based
Definition 1.1. For C a 1-complex define the combinatorial horoball C
(0)
on C to be the 1-complex with vertex set C × {0 ∪ N} and three types of edges:
1. One horizontal edge from (v, 0) to (w, 0) for each edge from v to w in C.
(Note that we allow vertices to be connected by multiple edges.)
2. For k ≥ 1 a horizontal edge from (v, k) to (w, k) whenever 0 < d(v, w) ≤
2k .
3. A vertical edge from (v, k) to (v, k+1) for each v ∈ C (0) and each k ∈ Z≥0 .
b → R≥0 sending a vertex (v, k) to k and
We define a height function h : C
interpolating linearly along edges.
5

Definition 1.2. If Γ, S and H are as above then the cusped space X associated
to this triple is defined as follows. For H in H let TH be a left transversal of
H in Γ. For H in H and t in TH let CH,t be the full subgraph of Cay(Γ, S)
containing tH; note that this is isomorphic to Cay(H, H ∩ S). Then let X be
the union
[
Cd
Cay(Γ, S) ∪
H,t
H∈H,t∈TH

where we identify CH,t ⊂ Cay(Γ, S) with the part of Cd
H,t with height 0. Then
the height function defined on each horoball extends to a height function h : X →
R≥0 .
For k ≥ 0 the k-thick part Xk of X is defined to be h−1 [0, k]. We say that
a path γ in X is vertical if h ◦ γ is strictly monotonic and horizontal if h ◦ γ is
constant.
Definition 1.3. A (quasi-)isometric embedding α from a subinterval of R to
X is called a (quasi)-geodesic. If that interval is closed and bounded then α is
a segment. If the interval is [0, ∞) then α is a ray. If the interval is all of R
then α is bi-infinite.
X is called a geodesic space if for any x and y in X there exists a geodesic
segment α : [a, b] with α(a) = x and α(b) = y.
Definition 1.4. A geodesic metric space X is δ-hyperbolic if every edge of any
geodesic triangle in X is contained in a δ-neighbourhood of the union of the
other two edges.
Definition 1.5. Γ is hyperbolic relative to H if the cusped space associated to
(Γ, S, H) is hyperbolic for some (equivalently for any) generating set S in which
S ∩ H is a generating set for H for each H ∈ H.
This definition of relative hyperbolicity is shown to be equivalent to several
other standard definitions in [22].
We recall a lemma from [7] that characterises hyperbolicity of the pair (Γ, H)
when Γ is itself a hyperbolic group. Recall that a collection H of subgroups of
Γ is almost malnormal if, for H1 and H2 in H and g in Γ, H1 ∩ gH2 g −1 is finite
unless H1 = H2 and g ∈ H1 .
Lemma 1.6. [7, Theorem 7.11] Let Γ be a non-elementary hyperbolic group
and let H be a finite set of subgroups of Γ. Then Γ is hyperbolic relative to H if
and only if H is almost malnormal in Γ and each element of H is quasi-convex
in Γ.
In the cases of interest to us all groups in H are virtually cyclic. A virtually
cyclic subgroup of a hyperbolic group is always quasi-convex, and is almost
malnormal if and only if it is maximal among virtually cyclic subgroups of Γ.
Putting this together with Lemma 1.6 we obtain the following:
Lemma 1.7. If Γ is hyperbolic and each group in H is maximal virtually cyclic
then Γ is hyperbolic relative to H.
Fix X as in Definition 1.2 and assume that it is δ-hyperbolic. We shall
require the following two lemmas describing the geometry of X. The first is [14,
Lemma 2.11] and the second is the Morse lemma for a hyperbolic metric space.
6

Lemma 1.8. Let C = 3δ. For any v in X0 and x in X there is a geodesic ray
starting at v that passes within a distance C of x.
Lemma 1.9. There exists a (computable) function D(λ, , δ) such that whenever
γ is a geodesic and γ 0 is a (λ, )-quasi-geodesic with the same end points in
X ∪ ∂X the Hausdorff distance from γ to γ 0 is at most D.
Fixing δ so that X is δ-hyperbolic we fix the constant C = 3δ and function
D = D(λ, , δ) as in Lemmas 1.8 and 1.9 for the remainder of this and the
following section.
We shall need an algorithm to compute the constant δ with respect to which
the cusped space is δ-hyperbolic. This is dealt with by the following results.
Proposition 1.10. [13, Prop. 2.3] There is an algorithm that takes as input a
presentation for a group Γ, the generators in Γ for a finite set of subgroups of Γ
with respect to which Γ relatively hyperbolic, and a solution to the word problem
in Γ and returns the constant of a linear relative isoperimetric inequality satisfied
by the given presentation of Γ.
In the case of interest here, Γ is hyperbolic. Hyperbolic groups have uniformly solvable word problem, so the requirement that the algorithm be given
a solution to the word problem in Γ is no restriction to its applicability.
The linear relative isoperimetric inequality satisfied by the group is closely
related to a linear combinatorial isoperimetric inequality satisfied by the conedoff Cayley complex. The definition of this space is [22, Definition 2.47].
In [22] the cusped 2-complex is defined; this is a simply connected 2-complex,
the 1-skeleton of which is the cusped 1-complex defined in Definition 1.2. The
length of the attaching map of each 2-cell in this complex is bounded above by
the maximum of 5 and the length of the longest relator in the given presentation
for Γ.
Theorem 1.11. [22, Theorem 3.24] Suppose that the coned-off Cayley complex of Γ with respect to S and H satisfies a linear combinatorial isoperimetric inequality with constant K. Then the cusped two-complex X associated to
the triple satisfies a linear combinatorial isoperimetric inequality with constant
3K(2K + 1).
The computation of δ from a presentation for Γ and a set of generators for
each group H in H is therefore completed by the following proposition:
Proposition 1.12. [22, Prop. 2.23] Suppose that a 2-complex X is simply
connected, that each attaching map has length at most M and that X satisfies
a linear combinatorial isoperimetric inequality. Then the 1-skeleton X (1) of X
is δ-hyperbolic for some δ and this δ is computable from M and the constant of
the isoperimetric inequality.

1.2

The Bowditch boundary

Definition 1.13. Let X be a hyperbolic geodesic metric space. The Gromov
boundary ∂X of X is defined to be the quotient of the set of geodesic rays
starting at some chosen base point in which two rays are identified if they are a
finite Hausdorff distance apart. It is endowed the quotient of the compact-open
topology.
7

This definition is quasi-isometry invariant and independent of the chosen
base point up to homeomorphism.
Definition 1.14. Let Γ be a group that is hyperbolic relative to a collection
H of subgroups. The Bowditch boundary ∂(Γ, H) is defined to be the Gromov
boundary of the cusped space associated to Γ and H with some generating set.
This definition of the Bowditch boundary is shown to be equivalent to other
definitions in [7]. If each group in H is maximal virtually cyclic then we have
the following description of the Bowditch boundary from [17]:
Lemma 1.15. If Γ is hyperbolic and each group in H is maximal virtually cyclic
then ∂(Γ, H) is the quotient of ∂(Γ, ∅) by the equivalence relation in which x ∼ y
if and only if either x = y or {x, y} = g · ΛH for some g in Γ and H in H. The
topology on ∂(Γ, H) is the quotient of the topology on ∂(Γ, ∅).
The boundary of a hyperbolic metric space has a natural quasi-conformal
class of metrics. Recall the definition of the Gromov product of a pair of points
p and q in X with respect to a base point v in X:
(p · q)v =

1
(d(v, p) + d(v, q) − d(p, q)).
2

This definition is extended to allow p and q to be in X ∪ ∂X by
(p · q)v = sup lim inf (pi · qj )v .
i,j→∞

Here the supremum is taken over pairs of sequences (pi ) and (qj ) in X converging
to p and q respectively.
By [9, III.H.3.21] ∂X admits a visual metric at any base point v; that is, a
metric dv on ∂X satisfying
k1 a−(p·q)v ≤ dv (p, q) ≤ k2 a−(p·q)v .
√
Here a, k1 and k2 can be taken to be 21/4δ , 3 − 2 2 and 1 respectively.

1.3

The double-dagger condition

If the boundary of X does not contain a cut point then its local connectivity
is controlled by the so-called double-dagger condition. This was defined first in
the absolute case in [2] and later in the relative case in [14]. We now record the
definition of the condition and some important properties. Fix a base point v
in X0 .
Let M = 6(C + 45δ) + 2δ + 3. For  ≥ 0 we say that a pair of points x and
y in X satisfy ? if |d(v, x) − d(v, y)| ≤  and d(x, y) ≤ M .
For n ≥ 0 we say that a pair of points x and y satisfying ? satisfy ‡(, n)(x, y)
if there exists a path of length at most n from x to y that avoids the ball of
radius m−C −45δ +3 centred at v, where m = min{d(v, x), d(v, y)}. After this
section we will not need to allow  to be non-zero; we will say that X satisfies
‡n if ‡(0, n)(x, y) holds for all x and y in X satisfying ?0 . However, the full
definition is required in the proof of Proposition 1.16.
We require the following proposition, which is essentially Proposition 5.1
of [14].
8

Proposition 1.16. Suppose that ∂(Γ, H) is connected and without a cut point.
Then there exists n such that X satisfies ‡n . Furthermore, there is an algorithm
that computes such an n if ∂(Γ, H) is connected and without a cut point and
that does not terminate if it is not connected.
For clarity we recall the proof of this proposition from [14] here.
Proof. We begin by recalling some constants from [14]. In this paper these
constants will only appear in this proof. Let k = 2M , let K = 3(22M +3 )+M +3
and for any n let R(n) = 4(n + M ) + 3k + 50δ + 3. For each n ≥ K in turn, check
whether ‡(10δ, n)(x, y) holds for all pairs of vertices (x, y) in BallR(n) (v) ∩ Xk
satisfying ?10δ .
If ∂(Γ, H) is connected and does not contain a cut point then such an n exists
by [14, Lemma 4.2]. It is commented that ‡(10δ, n)(x, y) holds for all pairs of
vertices (x, y) in BallR(n) (v) satisfying ?10δ with x ∈
/ Xk in the first paragraph
of the proof of [14, Lemma 2.16]. Then [14, Corollary 4.6] says that X satisfies
‡n ; note that this corollary applies because the conclusion of [14, Lemma 2.16]
holds in the case of virtually cyclic peripheral subgroups.
If ∂(Γ, H) is disconnected then there is no n such that the condition ‡n holds
by [14, Lemma 4.1].

1.4

Cut points and pairs

We now investigate cut points and pairs in ∂X under the assumption that X
satisfies ‡n ; we assume that this condition holds for the remainder of this section.
We relate the existence of such a point or pair to the connectedness of thickened
cylinders around quasi-geodesics in X.
Let γ be a bi-infinite (λ, )-quasi-geodesic in X or a (λ, )-quasi-geodesic ray
passing through X0 in X. Fix a point v in γ ∩ X0 . Since γ is a quasi-geodesic,
its limit set, which we shall denote Λγ, is either a pair of points γ(±∞) or a
single point γ(∞) depending on whether γ is bi-infinite or a ray.
Recall the definitions C = 3δ and D = D(λ, , δ) as in Lemma 1.9.
We define a subset of X, the connectivity of which will be seen to reflect the
connectivity of ∂X − Λγ. For R ≥ 0 let NR (γ) be the closed R-neighbourhood
of γ and for 0 ≤ r ≤ R ≤ ∞ let Nr,R (γ) be {x ∈ X : r ≤ d(x, γ) ≤ R}. For
K ≥ 0 let CK (γ) be {x ∈ X : d(x, γ) = K}. Finally, for 0 ≤ r ≤ K ≤ R ≤ ∞
let Ar,R,K (γ) be the union of those connected components of Nr,R (γ) that meet
CK (γ). Note that Ar,R,K (γ) contains NK,R (γ).
For a component U of Ar,∞,K (γ) define its shadow S U to be the set of
points p in ∂X such that for any geodesic ray α from v to p, α(t) is in U for t
sufficiently large.
S
Lemma 1.17. Let r > D. Then U S U = ∂X − Λγ, where the union is taken
over the set of connected components of Ar,∞,K (γ). Furthermore, S U ∩S V = ∅
for distinct components U and V .
Proof. The statement that shadows are disjoint is clear from the definition. The
assumption that r > D ensures that when U is a subset of Ar,∞,K (γ), S U does
not contain a point in Λγ by Lemma 1.9.
If p is any point in ∂X − Λγ then any geodesic ray α from v to p diverges
arbitrarily far from γ, so d(α(t), γ) ≥ r + D for t at least some number t0 . Let

9

U be the component of Ar,∞,K (γ) that contains α(t) for t ≥ t0 . If α0 is another
geodesic ray from v to p then for any t there exists t0 such that d(α0 (t), α(t0 )) ≤ D
and then |t − t0 | is guaranteed to be at most D. If t ≥ t0 + D then t0 ≥ t0 , so
α0 (t) is in the same component of Ar,∞,K (γ) as α(t0 ), which is in U . Therefore
α0 (t) ∈ U for t ≥ t0 + D. It follows that p ∈ S U .
Lemma 1.18. Let U be a component of Ar,∞,K (γ). Then S U is non-empty as
long as K ≥ r + D + δ + C and r > D.
Proof. Let x ∈ CK (γ) ∩ U . Then by Lemma 1.8 there exists a geodesic ray
α from v and t ≥ 0 such that d(α(t), x) ≤ C. Any geodesic segment in X
from x to α(t) is contained in U , so α(t) ∈ U . Also d(α(t), γ) ≥ r + D + δ;
it follows from Lemma 1.9, hyperbolicity of X and the assumption that r > D
that d(α(t0 ), γ) ≥ r for t0 ≥ t, and therefore that α(t0 ) ∈ U for t0 ≥ t. As
in the proof of Lemma 1.17 it follows from this and the fact that r > D that
α(∞) ∈ S U .
Lemma 1.19. If U is a component of Ar,∞,K (γ), S U is closed and open in
∂X − Λγ as long as r > D.
Proof. Let p be a point in S U and let p = α(∞) where α is a geodesic ray
from v. For t ≥ 0 let Vt (α) be the set of end points of geodesic rays β from v
such that d(β(t), α(t)) < 2δ + 1. The collection of such sets as t varies forms a
fundamental system of neighbourhoods of p ∈ ∂X.
Then there exists t0 such that for t ≥ t0 , d(α(t), γ) ≥ r+2D+7δ+1. We claim
that Vt0 (α) ⊂ S U for t0 as defined in the previous paragraph. To see this, let
q ∈ Vt0 (α) and let β be a geodesic ray from v to q, so d(β(t0 ), α(t0 )) < 2δ+1. Let
β 0 be another geodesic ray from v with β 0 (∞) = q, so d(β 0 (t0 ), β(t0 )) < 4δ. Suppose that there exists t ≥ t0 such that β 0 (t) ∈
/ U . Then there exists t0 ≥ t0 such
0 0
that d(β (t ), γ) ≤ r; without loss of generality assume that d(β 0 (t0 ), γ|[0,∞) ) ≤ r.
Let γ 0 be a geodesic ray from v to γ(∞), so the Hausdorff between γ|[0,∞) and
γ 0 is at most D. Then d(β 0 (t0 ), γ 0 ) ≤ r + D and d(β 0 (t0 ), γ 0 ) ≤ r + D + δ.
Putting these inequalities together, d(α(t0 ), γ) ≤ r + 2D + 7δ + 1, which is a
contradiction. Hence β(t) ∈ U for t ≥ t0 , and so q ∈ S U .
Since p was arbitrary in S U , it follows that S U is open. As U ranges over
the connected components of Ar,∞,K (γ), S U ranges over a cover of ∂X − Λγ
by disjoint open subsets (since r > D), so each is also closed.
The proof of the following lemma is based on the proof of [2, Proposition
3.2].
Lemma 1.20. If U is a connected component of Ar,∞,K (γ) then S U is contained in one connected component of ∂X −Λγ as long as r satisfies the following
inequality.


k2 n − 1
r > 2 loga
+ M + 12δ + D.
k1 1 − a−1
Proof. Let p and q be points in S U and let α1 and α2 be geodesic rays from v to
p and q respectively. Then there exist t1 and t2 such that α1 (t1 ) and α2 (t2 ) are
in U . Let φ : [0, `] → X be a path in U parametrised by arc length connecting
the two points α1 (t1 ) and α2 (t2 ).

10

For each integer i in [0, `] let zi be a point within a distance C of φ(i) so
that there is a geodesic ray βi from v with βi (mi ) = zi ; we can assume that
β0 = α1 and β` = α2 . Then, following the argument of [2, Prop. 3.2], we show
that ri (∞) and ri+1 (∞) can be connected in ∂X − Λγ for each i; for notational
convenience we prove it for i = 0.
Using the condition ‡n , define geodesic rays βt for each n-adic rational t in
[0, 1] inductively on the power k of the denominator of t to satisfy:

d βj/nk (mi + k), βj+1/nk (mi + k) ≤ M for each j with 0 ≤ j ≤ nk − 1.
Note that the first step of the induction holds since M is at least 2C + 1. The
triangle inequality gives the following lower bound on the Gromov product of
these points.


βj/nk (∞) · βj+1/nk (∞) v ≥ lim inf βj/nk (n1 ) · βj+1/nk (n2 ) v
n1 ,n2

≥ βj/nk (m0 + k) · βj+1/nk (m0 + k) v
= m0 + k − M/2
Let dv be a visual metric on ∂X with base point v, visual parameter a and
multiplicative constants k1 and k2 . We obtain:

dv βj/nk (∞), βj+1/nk (∞) ≤ k2 a−m0 −k+M/2 .
(*)
Inductively applying the triangle inequality we arrive at the following inequality
dv (β0 (∞), βt (∞)) ≤

k2 (n − 1)a−m0 +M/2
1 − a−1

for each n-adic rational t ∈ [0, 1].

Define a path ψ : [0, 1] → ∂X with ψ(t) = βt (∞) for each n-adic rational t in
[0, 1]; this extends continuously to a path from β0 (∞) to β1 (∞) by the uniform continuity of the map t → βt (γ) defined on the n-adic rationals, which
is established by equation (∗). This path is contained in the ball of radius
k2 (n − 1)a−m0 +M/2 /(1 − a−1 ) around β0 (∞).
We now bound below the distance dv (β0 (∞), Λγ). Let γ 0 be a geodesic ray
from v to γ(∞), so the Hausdorff distance between γ and γ 0 is at most D. By [9,
III.H.3.17],
(β0 (∞) · γ 0 (∞))v ≤ lim inf (β0 (n1 ) · γ 0 (n2 ))v + 2δ.
n1 ,n2

Let n1 and n2 each be at least m0 . Certainly d(β0 (m0 ), γ 0 ) > δ since r > δ + D,
so there exists a point p on [β0 (n1 ), γ 0 (n2 )] within a distance δ of β0 (m0 ). In
fact, d(β0 (m0 ), γ) > 2δ + D, so d(β0 , γ 0 (m0 )) > 2δ. Therefore there exists a
point q on [β0 (n1 ), γ 0 (n2 )] within a distance δ of γ 0 (m0 ).
Suppose that q is closer to β0 (n1 ) than p. Then by considering the geodesic
triangle with vertices β0 (n1 ), β0 (m0 ) and p we see that q is within distance 2δ
of β0 , and therefore the distance from γ 0 (m0 ) to β0 (m0 ) is at most 6δ. But
we assumed that r > 6δ + D, which gives a contradiction. This implies that
d(β0 (n1 ), γ 0 (n2 )) is equal to the sum of the distances d(β0 (n1 ), p), d(p, q) and
d(q, γ 0 (n2 )).
11

Then we have the following inequality.
(β0 (n1 ) · γ 0 (n2 ))v − (β0 (m0 ) · γ 0 (m0 ))v = d(β0 (n1 ), β0 (m0 )) − d(β0 (n1 ), p)
+ d(β0 (m0 ), γ 0 (m0 )) − d(p, q)
+ d(γ 0 (m0 ), γ 0 (n2 )) − d(q, γ 0 (n2 ))
≤ δ + 2δ + δ = 4δ
This implies a lower bound on the distance from β0 (∞) to γ(∞) with respect
to the visual metric.
dv (β0 (∞), γ(∞)) ≥ k1 a−m0 +(r−D)/2−6δ .
In the case that γ is bi-infinite, dv (β0 (∞), γ(−∞)) similarly satisfies the same
bound. Therefore, by the assumption on r the path constructed from β0 (∞) to
β1 (∞) avoids Λγ.
Lemma 1.21. The inclusion map Ar,R,K (γ) ,→ Ar,∞,K (γ) induces a bijection
between the sets of connected components of those subspaces of X as long as
R ≥ 4δ + D + max{r + 4δ + 1, K}.
Proof. Surjectivity is clearly guaranteed by the fact that R ≥ K. For injectivity,
let x and y be points in CK (γ) that lie in the same connected component of
Ar,∞,K (γ). We show that the shortest path from x to y in Nr,∞ (γ) stays within
a distance R of γ. Let φ : [0, `] → X be such a shortest path parametrised by
arc length. Suppose that d(φ(s), γ) > R. Let [t0 , t1 ] be a maximal subinterval
of [0, `] containing s such that d(φ(t), γ) ≥ r + 4δ + 1 for t ∈ [t0 , t1 ].
Then for t ∈ [t0 , t1 ], φ|[t−4δ−1,t+4δ+1]∩[t0 ,t1 ] has image in Nr+4δ+1,∞ (γ).
Therefore any geodesic segment from φ(min{t − 4δ − 1, t0 }) to φ(max{t +
4δ + 1, t1 }) is contained in Nr,∞ (γ), so by minimality of the length of φ,
φ|[t−4δ−1,t+4δ+1]∩[t0 ,t1 ] is a geodesic. This means that φ|[t0 ,t1 ] is an (8δ + 2)-local
geodesic. Therefore by [9, III.H.1.13] it is contained in a 2δ-neighbourhood of
any geodesic from φ(t0 ) to φ(t1 ).
By maximality of [t0 , t1 ], either d(φ(t0 ), γ) = r +4δ +1 or t0 = 0, so certainly
d(φ(t0 ), γ) ≤ max{r + 4δ + 1, K}, and similarly d(φ(t1 ), γ) satisfies the same
inequality. By δ-hyperbolicity applied to the geodesic quadrilateral with vertices
φ(t0 ), φ(t1 ) and the points γ(s0 ) and γ(s1 ) on γ minimising the distances to
φ(t0 ) and φ(t1 ), any geodesic from φ(t0 ) to φ(t1 ) is contained in a 2δ + max{r +
4δ + 1, K} neighbourhood of a geodesic from γ(s0 ) to γ(s1 ), so is a subset of
N2δ+max{r+4δ+1,K}+D (γ). Hence d(φ(s), γ) ≤ 4δ + max{r + 8δ + 2, K} + D,
which is a contradiction.
From the results of this section we conclude the following:
Proposition 1.22. The map that sends a component U of Ar,R,K (γ) to the
shadow (with respect to some base point v ∈ γ) of the component of Ar,∞,K (γ)
containing U is a well defined bijection between the set of connected components
of Ar,R,K (γ) and the set of connected components of ∂X − Λγ as long as r, R
and K are taken to simultaneously satisfy the conditions of lemmas 1.17, 1.18,
1.19, 1.20 and 1.21.
Remark 1.23. The conditions on r, R and K depend only on δ, n, λ and 
and suitable values can be computed from these data.
12

We end this section with the following lemma, which shows that connectedness of Ar,R,K (γ) can be detected locally.
Lemma 1.24. Suppose that γ is a bi-infinite (λ, )-quasi-geodesic and that neither point in Λγ is a cut point. Let r and R be chosen to satisfy lemmas 1.20
and 1.21. Let T be at least loga (2k1 /k2 ) + 3D + 2δ + K. Then every component
of Ar,R,K (γ) meets CK (γ) ∩ BallT (γ(t)) for any t such that γ(t) is in X0 .
Proof. Fix the base point v = γ(t). Let U be a component of Ar,R,K (γ) and let
U 0 be the component of Ar,∞,K (γ) containing U . Then it is sufficient to show
that U 0 meets CK (γ) ∩ BallT (v) since U 0 ∩ CK (γ) = U ∩ CK (γ) by Lemma 1.21.
Suppose that U 0 does does not meet CK (γ) ∩ BallT (v). Let p be a point in
S U and let α be a geodesic ray from v to p. Then α(s) ∈ U ∩ CK (γ) for some
s; by assumption d(α(s), v) ≥ T .
Let γ 0 be a geodesic connecting the points of Λγ so that the Hausdorff
distance between γ and γ 0 is at most D. Parametrise γ 0 so that d(γ 0 (0), v) ≤ D.
Then d(α(s), γ 0 ) ≤ K + D; let d(α(s), γ 0 (s0 )) ≤ K + D. This implies that
d(γ 0 (s0 ), v) ≥ T − D − K. We therefore have
(α(s) · γ 0 (s0 ))v ≥ T − D − K.
Assume that s0 ≥ 0; this implies that
(p · γ 0 (∞))v ≥ lim inf (α(m) · γ 0 (n))v
m,n→∞

≥ (α(s) · γ 0 (s0 ))v − D
≥ T − 2D − K.
So dv (p, γ 0 (∞)) ≤ k2 a−T +2D+K . Similarly, if s0 ≤ 0, dv (p, γ 0 (−∞)) ≤ k2 a−T +2D+K .
Therefore S U 0 is contained in a k2 a−T +2D+K neighbourhood of Λγ. Also, for
any s, the geodesic from γ(t + s) to γ(t − s) passes within a distance D of
γ(t), so (γ(t + s) · γ(t − s))v ≤ D. Then (γ(∞) · γ(−∞))v ≤ 2δ + D, and so
dv (γ(∞), γ(−∞)) ≥ k1 a−(2δ+D) . It follows by the inequality satisfied by T
that the closed balls of radius k2 a−T +2D+K around γ(∞) and γ(−∞) are disjoint. By Lemma 1.20 S U 0 is connected, so is contained in one of these two
balls, say in the ball around γ(∞). But then S U is a non-empty proper subset
of ∂X − {γ(∞)} that is closed and open, so γ(∞) is a cut point, which is a
contradiction.

2

Detecting cut points and pairs

We now use the results of the previous section to prove some computability
results concerting topological features of the Bowditch boundary of a hyperbolic
group under the assumption that the cusped space satisfies a double dagger
condition. These are the main technical results of this paper. The idea is to
identify the topological feature of the boundary with a combinatorial feature of
the cusped space of bounded size, so that the existence of that feature can be
determined by looking at only a finite part of the the cusped space.
Let Γ be a group hyperbolic relative to a finite set H of maximal virtually
cyclic subgroups. Let S be a generating set for Γ such that S ∩ H generates H
for each H in H. Let X be the cusped space associated to (Γ, H, S).
13

2.1

Geodesics in horoballs

First we must understand the connectivity of neighbourhoods of geodesics in the
thin part of X. We assume that the peripheral subgroups are virtually cyclic, so
the geometry of the cusps of X is relatively simple. For notational convenience
we initially restrict to the case in which X consists of a single cusp. Then the
vertex set of X can be identified with H ×Z≥0 and for any k there is an inclusion
of the Cayley graph Cay(H, S) ,→ h−1 (k) mapping a vertex h ∈ Cay(H, S) to
(h, k); for k = 0 this inclusion is an isomorphism of graphs.
Let dH be the word metric in Cay(H, S) and let Cay(H, S) be δH -hyperbolic
with respect to this word metric. Let α be a bi-infinite geodesic in Cay(H, S)
with respect to dH ; then any point in Cay(H, S) is within a distance of at most
2δH + 1 of α.
Let γ : [0, ∞) → X be a vertical geodesic ray with γ(0) = (α(0), 0). Then
for any k ∈ Z≥0 , the vertex set of h−1 (k) ∩ Nr,R (γ) is
{g ∈ H : 2k+r−1 ≤ dH (g, α(0)) ≤ 2k+R−1 } × {k}.
We will denote by Yk the set h−1 (k) ∩ Nr,R (γ).
Assume now that k ≥ log2 (2δH + 1). Then every vertex in h−1 (k), and
therefore every vertex in Yk , is adjacent to a vertex in α × {k}. Therefore Yk
contains connected components Yk+ and Yk− with
α|[2k+r−1 ,2k+R−1 ] × {k} ⊂ Yk+ ,
α|[−2k+R−1 ,−2k+r−1 ] × {k} ⊂ Yk− ,
and each of these components meets CK (γ). Therefore each of the sets Yk± is
a subset of a component of Ar,R,K (γ). Any vertex in the complement of these
two components of Yk is contained in
{g ∈ H : dH (g, α(0)) ≤ 2k+r } × {k}.
Therefore only those vertices of Yk that are in Yk+ ∪ Yk− are adjacent in X to
+
−
vertices of Yk+1 . Furthermore, Yk+ is adjacent to Yk+1
and not to Yk+1
and
−
±
likewise for Yk . Finally, vertices that are in Yk+1 but not in Yk+1 are adjacent
to vertices in Yk .
Thus, if k ≥ log2 (2δH + 1) then Ar,R,K (γ) ∩ h−1 [k, ∞) contains two un+
−
bounded components Y≥k
and Y≥k
containing ∪l≥k Yl+ and ∪l≥k Yl− respectively
and the complement of these two components is contained in
{g ∈ H : dH (g, α(0)) ≤ 2k+r } × {k}.
To make precise the consequences of this description of Ar,R,K (γ), we make
the following definition, now allowing X to consist of more than a single cusp.
Let γ : [a, b] → X be a geodesic segment such that h(γ(a)) = h(γ(b)) = k > R
such that h ◦ γ is decreasing at a and increasing at b. Let γ̂ : (−∞, ∞) → X
be the path obtained by concatenating γ with two vertical geodesic rays. Note
that this is a k-local-geodesic. Let A0r,R,K (γ) be
Ar,R,K (γ̂) − h−1 [k, ∞) ∩ NR (γ̂(−∞, a] ∪ γ̂[b, ∞)) .
14

The results of this section together give the following lemma, which we shall
use to control the depth to which geodesics in X connecting cut pairs in ∂X
penetrate into the thin part of X.
Lemma 2.1. Let γ and γ̂ be as in the previous paragraph. Let δH be such
that each H ∈ H is δH -hyperbolic with respect to the generating set H ∩ S.
Suppose that h(γ(a)) = h(γ(b)) ≥ min{R, log2 (2δH + 1)}. Then the inclusion
A0r,R,K (γ) ,→ Ar,R,K (γ̂) induces a bijection between the sets of connected components of those spaces.

2.2

Cut points

We now show that there is an algorithm that determines whether or not ∂X
contains a cut point under the assumption that X satisfies a double dagger
condition.
Proposition 2.2. There is an algorithm that takes as input a presentation for
a hyperbolic group Γ with generating set S, a list of subsets of S generating a
collection H of maximal virtually cyclic subgroups of Γ and integers δ and n such
that the cusped space is δ-hyperbolic and satisfies ‡n and returns the answer to
the question “does ∂(Γ, H) contain a cut point?”
Proof. It is shown in [4, Theorem 0.2] that any cut point in ∂(Γ, H) must be
the limit point of gHg −1 for some H ∈ H and g ∈ Γ. Therefore it is sufficient to
check whether or not ΛH is a cut point for each H ∈ H. Choose r, R and K to
simultaneously satisfy the conditions of lemmas 1.17, 1.18, 1.19, 1.20 and 1.21
with λ = 1 and  = 0. Let δH be large enough that each H in H is δH -hyperbolic
with respect to the generating set S ∩ H and let k ≥ log2 (2δH + 1).
Then for each vertical geodesic ray γ starting at the identity element 1 ∈ X0
check whether or not Ar,R,K (γ) ∩ h−1 ([0, k]) is connected; as in Lemma 2.1, it is
connected if and only if Ar,R,K (γ) is connected. Also, Ar,R,K (γ) is disconnected
if and only if Λγ = ΛH is a cut point by lemmas 1.17, 1.18, 1.19, 1.20 and 1.21,
where H is the element of H such that the combinatorial horoball based on
H ⊂ Cay(X, S) contains γ. This check can be completed in finite time.

2.3

Cut pairs

We now assume that X is δ-hyperbolic and satisfies ‡n , that ∂X contains no cut
point and that the Cayley graph of H with respect to its generating set S ∩ H
is δH -hyperbolic for each H in H. Then all results of sections 1.4 and 2.1 can
be applied.
First we show that the existence of a cut pair in ∂X is equivalent to the
existence of a feature in X of known bounded size. Then by searching for such
a feature one can determine whether or not ∂X contains a cut pair. We use
a pumping lemma argument: we aim to replace an arbitrary geodesic joining
the two points in a cut pair in ∂X with a periodic quasi-geodesic with bounded
period that also joins the points of a (possibly different) cut pair.
Before stating the proposition we define some constants. Take λ and  so
that any (8δ + 1)-local-geodesic is a (λ, )-quasi-geodesic; for example let λ =
(12δ + 1)/(5δ + 1) and let  = 2δ. Fix r, R and K to simultaneously satisfy the

15

conditions of propositions 1.17, 1.18, 1.19, 1.20 and 1.21 and fix T to satisfy the
conditions of Lemma 1.24 with this choice of λ and . Also let
k = max{8δ + 1, log2 (2δH + 1), T + R},
ρ = (2R + )λ2 +  + R and
η = max{(8δ + 1)/2, λ(T + K) + λ, λ(R + r) + λ, λ(R + ρ) + λ}.
Let B be the maximum valence of any vertex in Xk+R and let V be the maximum
number of vertices in any ball of radius ρ around any vertex in Xk+R . Then
define
Nmin = max{8δ + 1, λ(2R + 1) + λ + 1} and
Nmax = Nmin (k + R + 1) B 2η 2V + 1.
Proposition 2.3. ∂X contains a cut pair if and only if X contains one of the
following two features:
1. A short period geodesic at shallow depth in X: a geodesic segment γ : [a −
η, b + η] → X contained in Xk+R such that
(a) Nmin ≤ b − a ≤ Nmax ,
(b) h(γ(a)) = h(γ(b)), so there exists g ∈ Γ such that γ(b) = g · γ(a),
(c) γ|[b−η,b+η] = g · γ|[a−η,a+η] ,
(d) there is a partition P of the vertices of Nr,R (γ) ∩ NR (γ|[a,b] ) into two
subsets such that adjacent vertices lie in the same subset and each of
the sets meets CK (γ) ∩ BallT (γ(c)) for some c ∈ [a, b], and
(e) the partition on the vertices of Nr,R (γ) ∩ Ballρ (γ(b)) induced by the
restriction of P to that subset is the same as the translate by g of
the partition on the vertices of Nr,R (γ) ∩ Ballρ (γ(a)) obtained by the
restriction of P; note that Nr,R (γ)∩Ballρ (γ(b)) is equal to g·Nr,R (γ)∩
Ballρ (γ(a)) by condition 1c.
2. A short horseshoe-shaped geodesic: a geodesic segment γ : [a, b] → X such
that
(a) b − a ≤ Nmax − 2R + 2η
(b) h(γ(a)) = h(γ(b)) ≥ k,
(c) h ◦ γ is decreasing at a and increasing at b,
(d) A0r,R,K (γ) is disconnected.
Proof. First suppose that the first type of feature exists in X. Define a path γ 0
in X by
γ 0 ((b − a)m + t) = g m γ(a + t)
for m ∈ Z and t ∈ [0, b − a]. γ 0 is an (8δ + 1)-local-geodesic by condition 1c
since η ≥ (8δ + 1)/2. It is therefore a (λ, )-quasi-geodesic by [9]. We now aim
to show that Ar,R,K (γ 0 ) is disconnected.

16

S
Note that NR (γ 0 ) is a union m∈Z g m · NR (γ|[a,b] ) of translates of neighbourhoods of γ. Since η ≥ λ(R + r) + λ, Nr (γ 0 ) ∩ NR (γ|[a,b] ) is a subset of Nr (γ),
so is equal to Nr (γ) ∩ NR (γ|[a,b] ). Therefore Nr,R (γ 0 ) decomposes as a union
[

Nr,R (γ 0 ) =
g m · Nr,R (γ) ∩ NR γ|[a,b] .
m∈Z

Since b − a > λ(2R + 1) + λ, g m · NR (γ|[a,b] ) and g l · NR (γ|[a,b] ) contain
no adjacent vertices for |m − l| ≥ 2. Furthermore, if l = m + 1 then any
pair of adjacent vertices in these two sets is contained in g m · Ballρ (γ(b)) since
ρ ≥ (2R + )λ2 +  + R.
For each set U ∈ P define a set U 0 of vertices of Nr,R (γ 0 ) by letting u ∈ U 0 if
m
g u ∈ U for some m ∈ Z. This gives a well defined partition P 0 of the vertices
of Nr,R (γ 0 ) such that adjacent vertices lie in the same set by condition 1e. Its
restriction to Ar,R,K (γ 0 ) is non-trivial: CK (γ 0 ) contains CK (γ) ∩ BallT (γ(c))
since η ≥ λ(T + K) + λ and this set meets both sets in P 0 by condition 1d;
therefore Ar,R,K (γ 0 ) is disconnected and therefore Λγ 0 is a cut pair by the results
of section 1.4.
Now suppose that the second type of feature exists in X. Let γ̂ be the
(8δ + 1)-local-geodesic obtained by concatenating γ with vertical geodesic rays.
Then Ar,R,K (γ̂) is disconnected by Lemma 2.1 and Λγ̂ is a cut pair by the
results of section 1.4.
Conversely, suppose that ∂X does contain a cut pair. Let γ 0 be a geodesic in
X such that Λγ 0 is a cut pair. Assume first that some connected component of
γ 0−1 h−1 [0, k + R] is an interval of length less than Nmax + 2η, say [a − R, b + R]
with h(γ 0 (a − R)) = h(γ 0 (b + R)) = k + R, so h(γ 0 (a)) = h(γ 0 (b)) = k. Let
γ = γ 0 |[a,b] . Let c ∈ [a, b] such that h(γ 0 (c)) = 0. Ar,R,K (γ 0 ) is disconnected and
each component meets CK (γ 0 ) ∩ BallT (γ 0 (c)) by Lemma 1.24. Since k ≥ T this
is a subset of A0r,R,K (γ), and A0r,R,K (γ) is a subset of Ar,R,K (γ 0 ), so A0r,R,K (γ)
is disconnected. Therefore γ 0 is a feature of the second kind described in the
proposition.
On the other hand, suppose that some interval [−η, Nmax + η] is a subset
of γ 0−1 h−1 [0, k + R]. Then there exist a0 < a1 < · · · < a2V in [0, Nmax ] such
that h(ai ) = h(aj ) for all i and j, so ai = gi a0 for some gi ∈ Γ, such that
γ 0 |[ai −η,ai +η] = gi · γ 0 |[a0 −η,a0 +η] , and such that ai − ai−1 ≥ Nmin . Let P 0 be a
partition of the vertices of Nr,R (γ 0 ) into two subsets such that adjacent vertices
are in the same set and so that both sets meet CK (γ 0 ). Such a partition exists
by the results of section 1.4 since Λγ 0 is a cut pair. Since η ≥ λ(R + ρ) + λ,
Nr,R (γ 0 ) ∩ Ballρ (γ(a0 )) is equal to gi−1 Nr,R (γ 0 ) ∩ Ballρ (γ(ai )) for all i. This set
contains at most V vertices, so there exist 0 ≤ i < j ≤ 2V such that
gi−1 P 0 |Nr,R (γ 0 )∩Ballρ (γ(ai )) = gj−1 P 0 |Nr,R (γ 0 )∩Ballρ (γ(aj )) .
Let a = ai and b = aj and let γ = γ 0 |[a−η,b+η] . We claim that γ is then a
feature of the first kind described in the proposition. Setting g = gj gi−1 and
P = P 0 |Nr,R (γ 0 )∩NR (γ|[a,b] ) , conditions 1a, 1b, 1c and 1e are satisfied by definition
of the ai . Let c ∈ [a, b] such that γ 0 (c) ∈ X0 . Then CK (γ) ∩ BallT (γ(c)) is equal
to CK (γ 0 ) ∩ BallT (γ 0 (c)) since η ≥ λ(T + K) + λ and Lemma 1.24 guarantees
that both sets in P 0 meet this set, so condition 1d is satisfied, too.
The existence of a geodesic segment with the properties described in the
statement of Proposition 2.3 can be checked by looking at just a finite ball
17

in X. Such a ball can be computed from a solution to the word problem in
Γ, which exists since Γ is hyperbolic. Therefore we immediately obtain the
following corollary:
Corollary 2.4. There is an algorithm that takes as input a presentation for
a hyperbolic group Γ with generating set S, a list of subsets of S generating a
collection H of maximal virtually cyclic subgroups of Γ and integers δ, δH and
n such that the cusped space associated to (Γ, H, S) is δ-hyperbolic and satisfies
‡n and such that the Cayley graph of each element of H with respect to its given
generating set is δH -hyperbolic and returns the answer to the question “does
∂(Γ, H) contain a cut pair?”

2.4

Non-cut pairs

By a similar argument, we now show that there is an algorithm that determines
whether or not ∂X contains a non-cut pair. For the detection of non-cut pairs
we will need the following lemma.
Lemma 2.5. Suppose that ∂X does not contain a cut point. Let (xn )n∈Z be a
sequence of points in X with xn → x±∞ as n → ±∞. Suppose that each pair
{xn , xn+1 } is a cut pair. Then so is {x−∞ , x∞ }.
Proof. ∂X is locally connected by the main theorem of [3]. ∂X is assumed not
to contain a cut point, so the results of sections 2 and 3 of [8] can be applied.
We recall some definitions from that paper. For x ∈ ∂X we define val(x) ∈ N to
be the number of ends of ∂X −{x}. Then we let M (n) = {x ∈ ∂X : val(x) = n}
and M (n+) = {x ∈ ∂X : val(x) ≥ n}. For x and y in M (2) we write x ∼ y if
x = y or {x, y} is a cut pair; this defines an equivalence relation. For x and y
in M (3+) we write x ∼
= y if val(x) = val(y) and ∂X − {x, y} has exactly val(x)
components.
Recall [8, Lemma 3.8]: if x ∼
= y and x ∼
= z then y ∼
= z. Therefore xn ∈ M (2)
for all n, so {xn }n∈Z is a subset of a ∼-equivalence class σ. By [8, Lem. 3.2] σ
is a cyclically separating set, and so is the closure of σ by [8, Lem. 2.2], which
implies that {x−∞ , x∞ } is a cut pair as required.
Let λ, , r, R, K, T , k, ρ, η, B and V be as defined in section 2.3. Let N1 ,
N2 and N3 be given by
N1 = 2(V − 1)((k + R + 1)B 2η V V +1 + 2η) + 2η + 2((k + R + 1)B 2η + 1),
N2 = (k + R + 1)B 2η + 1,
N3 = 2(k + R + 1)B 2η V V +1 + 4η.
Proposition 2.6. ∂X contains a non-cut pair if and only if X contains one of
the following two features:
1. Geodesic segments γi : [ai − η, bi + η] → X with image in Xk for i = 1, 2, 3
with a2 = b1 and a3 = b2 such that
(a) 1 ≤ bi − ai ≤ N1 for i = 1, 3,
(b) 1 ≤ b2 − a2 ≤ N2 ,
(c) γi |[bi −η,bi +η] = γi+1 |[ai −η,ai +η] for i = 1, 2,
18

(d) γi |[bi −η,bi +η] = gi · γi |[ai −η,bi +η] for i = 1, 3, and
(e) h(γi (ai )) = h(γi (bi )) for i = 1, 3, so there exist gi ∈ Γ such that
γi (bi ) = gi γ(ai ),
(f ) all vertices of CK (γ2 ) ∩ BallT (γ2 (c)) lie in the same connected component of Nr,R (γ2 ) ∩ NR (γ2 |[a2 ,b2 ] ) for some c ∈ [a2 , b2 ] such that
γ2 (c) ∈ X0 .
2. A geodesic segment γ : [a, b] → X with image in Xk such that
(a) b − a ≤ N3 ,
(b) h(γ(a)) = h(γ(b)) = k with γ descending vertically at a and ascending
vertically at b, and
(c) A0r,R,K (γ) is connected.
Proof. First suppose that X contains a feature of the first kind described in the
proposition. Then define a path γ 0 in X as follows:
 m
0
0
0

g1 · γ1 (t ) if t = m(b1 − a1 ) + t for m ∈ Z≤0 and t ∈ [a1 , b1 ]
γ 0 (t) =

if t ∈ [a2 , b2 ]

γ2 (t)




g3m

0

· γ3 (t )

if t = m(b3 − a3 ) + t0 for m ∈ Z≥0 and t0 ∈ [a3 , b3 ]

That is, γ 0 is obtained by concatenating infinitely many translates of γ1 , then a
copy of γ2 , then infinitely many translates of γ3 . Note that this is an (8δ + 1)local-geodesic by conditions 1c and 1d since η ≥ 8δ + 1 and is therefore a
(λ, )-quasi-geodesic.
CK (γ 0 ) ∩ BallT (γ 0 (c)) is equal to CK (γ2 ) ∩ BallT (γ2 (c)) since γ 0 |[a2 −η,b2 +η] =
γ2 and η ≥ λ(T + K) + λ. Furthermore, η ≥ λ(R + r) + λ, which similarly
guarantees that Nr,R (γ2 ) ∩ NR (γ2 |[a2 ,b2 ] ) is a subset of Nr,R (γ 0 ). Therefore
CK (γ 0 ) ∩ BallT (γ 0 (c)) lies in a single component of Ar,R,K (γ 0 ) by condition 1f,
so Ar,R,K (γ 0 ) is connected by Lemma 1.24, so Λγ 0 is a non-cut pair by the results
of section 1.4.
Now suppose that a feature of the second type exists in X. Let γ̂ be the
path obtained by concatenating γ with vertical geodesic rays. Then γ̂ is an
(8δ + 1)-local-geodesic since k ≥ 8δ + 1. Ar,R,K (γ̂) is connected by Lemma 2.1,
so Λγ̂ is a non-cut pair by the results of section 1.4.
Conversely, suppose that ∂X contains a non-cut pair. Let γ 0 be an (8δ + 1)local-geodesic in X such that Λγ 0 is such a pair. Assume first that γ 0 is contained
in Xk+R and reparametrise γ 0 so that γ 0 (0) ∈ X0 . CK (γ 0 )∩BallT (γ 0 (0)) contains
at most V vertices and lies in a single component of Nr,R (γ 0 ). Define n±
V to be
−
±λ(K +T +) and then for l decreasing from V −1 to 1 let n+
and
n
be
chosen
l
l
−
0
0
to minimise n+
−n
among
pairs
such
that
C
(γ
)∩Ball
(γ
(0))
meets
at
most
K
T
l
l
+
−
+
l components of Nr,R (γ 0 )∩NR (γ 0 |[n− ,n+ ] ) and [n−
,
n
]
⊂
[n
,
n
].
Note
that
l+1
l+1
l
l
l

l

0
0
the condition that |n±
l | ≥ λ(K + T ) + λ ensures that CK (γ ) ∩ BallT (γ (0)) is
0
0
a subset of Nr,R (γ ) ∩ NR (γ |[n− ,n+ ] ).
l

l

+
2η V +1
Suppose that n+
+ 2η. Let Q be the partition
l−1 − nl > (k + R + 1)B V
0
0
of CK (γ ) ∩ BallT (γ (0)) into l non-empty subsets induced by connectivity in
Nr,R (γ 0 )∩NR (γ 0 |[n− ,n+ −1] ). For each t ∈ [nl +η, nl−1 −η] define the following
l−1

l−1

19

sets:
Yt = Nr,R (γ 0 ) ∩ Ballρ (γ 0 (t))

Zt = Nr,R (γ 0 ) ∩ Ballρ (γ 0 (t)) ∪ NR (γ 0 |[n−



)
l−1 ,t]

and let Pt be the partition of the vertices of Yt into l+1 subsets: l corresponding
to the l sets in Q by connectivity in Zt and one containing the part of Yt not
connected to CK (γ 0 ) ∩ BallT (γ 0 (0)) in Zt . As in the proof of Proposition 2.3
+
there exist s1 < s2 in [n+
l + η, nl−1 − η] such that such that
1. h(γ 0 (s1 )) = h(γ 0 (s2 )), so γ 0 (s2 ) = gγ 0 (s1 ) for some g in Γ,
2. γ 0 |[s2 −η,s2 +η] = g · γ 0 |[s1 −η,s1 +η] , which implies that Ys2 = g · Ys1 , and
3. Ps2 = g · Ps1 .
Then replace γ 0 by another path defined by
( 0
γ (t)
00
γ (t) =
g −1 · γ 0 (t + (s2 − s1 ))

if t ≤ s1
if t ≥ s2

This is an (8δ + 1)-local-geodesic since η ≥ 8δ + 1. By definition of ρ, the
intersection of Zs2 and Nr,R (γ 0 ) ∩ NR (γ 0 |[s2 ,n+ ] ) is contained in Ys2 . Then by
l−1

0
0
definition of n+
). Since
l−1 , two distinct sets in Ps2 meet Nr,R (γ )∩NR (γ |[s2 ,n+
l−1 ]
η ≥ λ(R + r + ),

g −1 Nr,R (γ 0 ) ∩ NR (γ 0 |[s2 ,n+ ] ) = Nr,R (γ 00 ) ∩ NR (γ 0 |[s1 ,n+

l−1 −(s2 −s1 )]

l−1

),

and it follows that CK (γ 00 ) ∩ BallT (γ 0 (0)) meets at most l − 1 components of
Nr,R (γ 00 ) ∩ NR (γ 00 |[n− ,n+ −(s2 −s1 )] ). This implies that the process of replacing
l−1

l−1

−
0
0
γ 0 by γ 00 leaves unchanged n+
l0 for all l < l and nl0 for all l and strictly reduces
+
nl . Therefore by repeating this process we can assume that γ 0 was chosen to
±
2η V +1
ensure that |n±
+ 2η for all l, and
l−1 − nl | is at most (k + R + 1)B V
therefore that
2η V +1
|n±
+ 2η).
1 | ≤ λ(K + T + ) + (V − 1)((k + R + 1)B V
−
There exist a1 ≤ b1 ≤ n−
1 − η with n1 − b1 and b1 − a1 both at most
2η
(k + R + 1)B + 1 such that

1. h(γ 0 (b1 )) = h(γ 0 (a1 )), so γ 0 (b1 ) = g1 · γ 0 (a1 ) for some g1 ∈ Γ.
2. γ 0 |[b1 −η,b1 +η] = g1 · γ 0 |[a1 −η,a1 +η] .
Then let γ1 = γ 0 |[a1 −η,b1 +η] . Similarly define b3 ≥ a3 ≥ n+
1 and let γ3 =
γ 0 |[a3 −η,b3 +η] . Let a2 = b1 and b2 = a3 and let γ2 = γ 0 |[a2 −η,b2 +η] ; note that
b2 − a2 ≤ N1 . Then the triple (γ1 , γ2 , γ3 ) is a feature in X of the first kind listed
in the proposition: conditions 1a, 1b, 1e, 1c and 1d clearly hold by construction
and condition 1f holds because the condition that η ≥ λ(R + r) + λ ensures
that Nr,R (γ 0 ) ∩ NR (γ 0 |[n− ,n+ ] ) is a subset of Nr,R (γ2 ) ∩ NR (γ2 |[a2 ,b2 ] ).
1
1
If γ 0 is not contained in Xk+R let γ 0−1 h−1 [0, k + R] be a (possibly infinite)
union of (possibly infinite) intervals ∪i∈I [ai − R, bi + R] where we order the
20

intervals so that ai+1 > bi for all i. Then h(γ 0 (ai )) = h(γ 0 (bi )) = k for all i and
we can apply the results of section 2.1. For i ∈ I let γi0 = γ 0 |[ai ,bi ] . Let γ̂i0 be
the bi-infinite (8δ + 1)-local-geodesic obtained by concatenating γi with either
one or two vertical geodesic rays.
Suppose that Λγ̂i0 is a cut pair for all i. Then Lemma 2.5 tells us that Λγ 0
is a cut pair, which is a contradiction. Therefore there exists i such that Λγ̂i is
a non-cut pair.
Arguing as before, the geodesic γ̂i can be altered to ensure that bi − ai ≤
4η + 2(k + R + 1)B 2η V V +1 ; this yields a feature of the second type described
in the proposition.
From this we deduce the following corollary:
Corollary 2.7. There is an algorithm that takes as input a presentation for
a hyperbolic group Γ with generating set S, a list of subsets of S generating a
collection H of maximal virtually cyclic subgroups of Γ and integers δ, δH and
n such that the cusped space associated to (Γ, H, S) is δ-hyperbolic and satisfies
‡n and such that the Cayley graph of each element of H with respect to its given
generating set is δH -hyperbolic and returns the answer to the question “does
∂(Γ, H) contain a non-cut pair?”

3

Splittings of groups with circular boundary

The question of the existence of a relative splitting of a hyperbolic group cannot be answered by consideration of the topology of its boundary alone if the
boundary is homeomorphic to a circle: some groups with circular boundary split
and some do not. In this section we deal with this special case.

3.1

Circular boundary

Let Γ by a hyperbolic group with a finite collection H of subgroups such that
Γ is hyperbolic relative to H and ∂(Γ, H) is homeomorphic to S 1 . Then Γ
acts as a discrete convergence group on ∂(Γ, H) by [5], so by the Convergence
Group Theorem of Tukia, Casson, Jungreis and Gabai [34, 11, 19] there is a
properly discontinuous action of Γ by isometries on H2 and a Γ-equivariant
homeomorphism ∂(Γ, H) → ∂H2 .
Let K be the (finite) kernel of the action of Γ on ∂(Γ, H); note that this
is the same as the kernel of the extension of the action to H2 . Then Γ is an
extension
1

K

Γ

Γ0

1

and the quotient Γ0 acts faithfully on H2 . Let H0 be the set of images of elements
of H in Γ0 .
Lemma 3.1. With Γ and Γ0 as above, Γ splits non-trivially over a virtually
cyclic subgroup relative to H if and only if Γ0 admits such a splitting relative to
H0 .

21

Proof. One direction is clear: if Γ0 acts minimally on a non-trivial tree T with
virtually cyclic edge stabilisers then the quotient map Γ → Γ0 induces a minimal
Γ-action on T with edge stabilisers finite extensions of the edge stabilisers of
the Γ0 -action.
Conversely, suppose that Γ acts minimally on a non-trivial tree T with virtually cyclic edge stabilisers. K is finite, so the restriction of the action to K
fixes a vertex v. K is normal, so its action fixes Γ · v pointwise. Any point in
T lies on a geodesic path connecting points in Γ · v, since the union of all such
paths is a Γ-invariant subtree of T and the action was assumed to be minimal.
Therefore K acts trivially on T .
It follows that the Γ-action descends to a Γ0 action, and the edge stabilisers
are quotients of the original edge stabilisers by finite subgroups. Furthermore,
elements of H0 are elliptic if elements of H are.
Any finite normal subgroup of Γ is contained in the ball of radius 4δ + 2
centred at the identity by [9], so by checking all finite subsets of this ball using
a solution to the word problem, the set of finite normal subgroups of Γ can be
computed. K is the unique maximal finite normal subgroup of Γ and is therefore
computable.
As described above, Γ0 can be realised as a discrete subgroup of Isom H2 .
The conjugacy classes of elements of H0 are then precisely the conjugacy classes
of maximal parabolic subgroups of Γ0 . The action of Γ0 on ∂(Γ0 , H0 ) is minimal,
so the limit set of the action is S 1 . It follows that Γ0 is a Fuchsian group of the
first kind: H2 /Γ0 is a finite volume orbifold and H0 is a choice of conjugacy class
representatives for the cusp subgroups. Truncating the cusps of the orbifold, we
realise Γ0 as the fundamental group of a compact hyperbolic orbifold such that
H0 is a choice of conjugacy class representatives for the boundary subgroups.
Definition 3.2. A group is bounded Fuchsian if it acts properly discontinuously
and convex cocompactly (i.e. cocompactly on a convex subset) on H2 . Then
a group is bounded Fuchsian if and only if it surjects with finite kernel onto
the fundamental group of a compact two-dimensional hyperbolic orbifold. The
peripheral subgroups of a bounded Fuchsian group are the fundamental groups
of the boundary components of the associated orbifold.
Therefore we have shown that Γ0 is a bounded Fuchsian group and H0 is
a collection of representatives of its conjugacy classes of peripheral subgroups.
This proves the following lemma:
Lemma 3.3. There is an algorithm that, when given a presentation for a hyperbolic group with a set H of virtually cyclic peripheral subgroups, returns a
presentation for another hyperbolic group Γ0 with a set H0 of virtually cyclic
subgroups such that ∂(Γ0 , H0 ) is homeomorphic to ∂(Γ, H) and Γ splits over a
virtually cyclic subgroup relative to H if and only if Γ0 splits over a virtually
cyclic subgroup relative to H0 . Furthermore, if ∂(Γ0 , H0 ) is homeomorphic to a
circle then Γ0 is the fundamental group of a compact two-dimensional hyperbolic
orbifold and H0 is a set of representatives of fundamental groups of components
of the boundary of the orbifold.

22

3.2

Orbifolds

Given the results of the previous section, the problem of determining whether or
not a given group Γ with circular boundary splits non-trivially over a virtually
cyclic subgroup relative to a collection H of peripheral subgroups reduces to
the case in which Γ is a bounded Fuchsian group and H is a set of conjugacy
class representatives of its peripheral subgroups. Let Γ = π1 Q where Q is a
compact hyperbolic orbifold, so H is a set of conjugacy class representatives of
the boundary subgroups of Q.
We recall some terminology to describe orbifolds. The universal cover of a
hyperbolic orbifold (possibly with boundary) is a convex subspace Q̃ of H2 . The
orbifold fundamental group π1 Q acts properly discontinuously and by isometries
on Q̃. The underlying topological surface Qtop of Q is defined to be the topological quotient of Q̃ by this action. The topological boundary ∂top of Q is the
boundary of Qtop , while the orbifold boundary ∂Q of Q is the image of the
boundary of Q̃ in Qtop under the quotient projection. A mirror in Q is the image in Qtop of the set of fixed points of an order 2 orientation reversing isometry
of Q̃ in π1 Q. All mirrors in Q are contained in ∂top Q and any mirror is homeomorphic either to a circle or to an interval. In the latter case each end point
of the interval is contained in either ∂Q or in another mirror. The intersection
of two mirrors is called a corner reflector ; the stabiliser in π1 Q of the preimage
in Q̃ of a corner reflector is a finite dihedral group. If x is a point in Q̃ whose
stabiliser in π1 Q is non-trivial, cyclic and orientation preserving then the image
of x in Qtop is called a cone point. The singular locus of Q is the union of all
mirrors, corner reflectors and cone points. If y is not contained in the singular
locus of Q then any preimage of y in Q̃ has trivial stabiliser in π1 Q.
A geodesic in Q is a curve γ that is the image of a geodesic γ̃ in Q̃ under
the quotient projection. A geodesic γ is closed if it is compact and simple if it
is closed and furthermore g · γ̃ is either equal to or disjoint from γ̃ for each g in
π1 Q. A simple closed geodesic is homeomorphic to either a circle or an interval
with each of its end points contained in a mirror in Q. A simple closed geodesic
is essential if it is not contained in ∂top Q. For more information about orbifolds
see [31].
The theory of splittings of fundamental groups of orbifolds relative to their
boundary subgroups is developed in [23]; we recall the following results:
Lemma 3.4. [23, Corollary 5.6] Γ splits non-trivially relative to H if and only
if Q contains an essential simple closed geodesic.
Definition 3.5. We call a compact orbifold without an essential simple closed
geodesic small.
Proposition 3.6. [23, Proposition 5.12] A hyperbolic 2-orbifold Q is small if
and only if it is one of the following.
∼ ha, b|ap , bq , abr i where p−1 +
1. A sphere with three cone points, so π1 Q =
−1
−1
q + r < 1 and the peripheral structure is empty.
2. A triangle, all three edges of which are mirrors, so π1 Q has presentation
ha, b, c|a2 , b2 , c2 , (ab)p , (bc)q , (ca)r i where p−1 + q −1 + r−1 < 1 and the
peripheral structure is empty.

23

3. A disc with two cone points, so π1 Q ∼
= ha, b|ap , bq i where p, q > 1 and the
peripheral structure is {habi}.
4. A cylinder with one cone point, so π1 Q ∼
= ha, b|(ab)p i where p > 1 and the
peripheral structure is {hai, hbi}.
5. A pair of pants, so π1 Q is the free group ha, b|i and the peripheral structure
is {hai, hbi, hci}.
6. A disc with one cone point with edge consisting of an interval boundary
component and a mirror, so π1 Q ∼
= ha, t|a2 , tp i where p > 1 and the
−1
peripheral structure is {ha, tat i}.
7. A square with an interval boundary component and three mirrors edges,
so π1 Q ∼
= ha, b, c|a2 , b2 , c2 , (ab)p , (bc)q i where p + q ≥ 1 and the peripheral
structure is {ha, ci}.
8. An annulus in which one edge comprises an interval boundary component
and a mirror and the other is a circular boundary component, so π1 Q ∼
=
ha, t|a2 i with peripheral structure {ha, tat−1 i}.
9. A pentagon with two non-adjacent interval boundary components and three
mirrors as edges, so π1 Q ∼
= ha, b, c|a2 , b2 , c2 , (ab)p i with peripheral structure {hb, ci, hc, ai}.
10. A hexagon, the six edges of which are alternately interval boundary components and mirrors, so π1 Q ∼
= ha, b, c|a2 , b2 , c2 i and the peripheral structure
is {ha, bi, hb, ci, hc, ai}.
Lemma 3.7. There is an algorithm that takes as input a presentation for a
hyperbolic group Γ and a collection H of maximal virtually cyclic peripheral
subgroups and terminates if and only if ∂(Γ, H) is homeomorphic to a circle
and Γ does not split relative to H over a virtually cyclic subgroup.
Proof. First use the algorithm of Lemma 3.3 and let the output of that algorithm
be (Γ0 , H0 ); then ∂(Γ, H) is homeomorphic to a circle and Γ does not split over
a virtually cyclic subgroup relative to H if and only if there is an isomorphism
from Γ0 to one of the groups with peripheral structure listed in proposition 3.6
that maps elements of H0 to conjugates of elements of that peripheral structure.
Enumerate the groups and peripheral structures described in Proposition 3.6
and, in parallel, enumerate all homomorphisms from these groups to Γ0 and
homomorphisms from Γ0 to these groups. Note that this is possible since one
can test whether or not a map defined on the generators of a group extends
to a homomorphism using a solution to the word problem in the codomain of
the map, and Γ0 and all groups listed in Proposition 3.6 are hyperbolic. The
algorithm then terminates when an inverse pair of such maps that preserve the
peripheral structures (up to conjugacy) is found.

4

Maximal splittings

We now apply the technical results of sections 2 and 3 to the problem of finding
a maximal splitting of a one-ended hyperbolic group.

24

4.1

JSJ decompositions

We begin by recalling the definition a JSJ decomposition. For a more detailed
account see [23]. Let Γ be a group and let A be a collection of subgroups of
Γ that is closed under conjugation and taking subgroups. Let H be another
collection of subgroups of Γ. An (A, H)-tree is a tree with a Γ-action with no
edge inversions in which the stabiliser of each edge is in A and each element of
H is elliptic, that is, it fixes a point in the tree. An (A, H)-tree T dominates
another such tree T 0 if there is a Γ-equivariant morphism from T to T 0 . T is
elliptic with respect to T 0 if the stabiliser of each edge in T is elliptic in T 0 . For v
a vertex of T we denote by Γv the stabiliser of v, and similarly if e is an edge of
T we let Γe denote the stabiliser of e. We will sometimes refer to a (A, H)-tree
as a splitting of Γ over A relative to H. A splitting is trivial if Γ is elliptic. We
will frequently implicitly move between the languages of group actions on trees
and graphs of groups.
Fixing A and H, a subgroup of Γ is universally elliptic if it is elliptic with
respect to any (A, H)-tree. An (A, H)-tree is universally elliptic if the stabiliser
of each if its edges is universally elliptic. An (A, H) tree is a JSJ tree if it
is universally elliptic and is maximal for domination among universally elliptic
(A, H) trees.

4.2

The Bowditch JSJ

In [8] Bowditch defines a canonical JSJ tree Σ for a one-ended hyperbolic group
Γ where A is the set of virtually cyclic subgroups of Γ and H is empty. (To
ensure that A is closed under taking subgroups we should strictly speaking also
include the finite subgroups of Γ in A. However, since Γ is assumed to be oneended it does not split over any finite subgroup, so this change is not important.)
We recall a description of the tree Σ here.
Σ is a tree with a three-colouring: its vertex set V (Σ) admits a partition
V1 (Σ) t V2 (Σ) t V3 (Σ) preserved by the action of Γ such that no two vertices in
either V1 (Σ) or V2 (Σ) ∪ V3 (Σ) are adjacent.
The stabiliser of a vertex in V1 (Σ) is a maximal virtually cyclic subgroup of
Γ and therefore contains the stabiliser of each incident edge at finite index.
To describe the vertices of the second type we require the following definition.
Recall definition 3.2 of a bounded Fuchsian group.
Definition 4.1. A hanging Fuchsian subgroup Q of Γ is a subgroup of Γ that
is the stabiliser of a vertex in some finite splitting of Γ over virtually cyclic
subgroups such that Q admits an isomorphism with a bounded Fuchsian group
that maps the stabilisers of incident edges precisely to the peripheral subgroups.
Stabilisers of vertices in V2 (Σ) are precisely the maximal hanging Fuchsian
subgroups of Γ and the stabilisers of incident edges at such a vertex in the
JSJ decomposition are precisely the peripheral subgroups referred to in the
definition.
The stabiliser of a vertex in V3 (Σ) is not virtually cyclic and is not a hanging
Fuchsian subgroup.

25

4.3

Splittings and the topology of the boundary

In this section we recall and extend some results linking the existence of a nontrivial splitting of a hyperbolic group relative to a collection of virtually cyclic
subgroups to the topology of a particular Bowditch boundary.
For the remainder of Section 4.3, we fix a hyperbolic group Γ and a collection
b
H of virtually cyclic subgroups. If H is any virtually cyclic subgroup of Γ, let H
b
be the unique maximal virtually cyclic subgroup of Γ containing H. Then let H
b
b
be {H|H ∈ H}. Recall Lemma 1.7: since each group in H is maximal virtually
b We may therefore study the boundary
cyclic, Γ is hyperbolic relative to H.
b
∂(Γ, H).
4.3.1

Boundaries with cut points

b contains a cut
We first recall results that deal with the case in which ∂(Γ, H)
point. First recall Bowditch’s definition [6] of a peripheral splitting.
Definition 4.2. If Γ is a group and H is a finite collection of subgroups of Γ,
a peripheral splitting of Γ with respect to H is a representation of Γ is a finite
bipartite graph of groups such that each vertex group of one colour is conjugate
to an element of H, and each element of H is conjugate to a vertex group of
that colour.
As for any splitting, we say that a peripheral splitting is trivial if some vertex
group is equal to Γ.
b is a
Note that, in our setting, a peripheral splitting of Γ with respect to H
splitting of Γ over virtually cyclic subgroups relative to H.
Then the following proposition, which we obtain by putting together two theorems of Bowditch, completes our treatment of the case in which the boundary
contains a cut point.
b is connected and contains a cut point.
Proposition 4.3. Suppose that ∂(Γ, H)
Then the pair Γ admits a non-trivial splitting over virtually cyclic subgroups
relative to H.
b is a parabolic fixed
Proof. By [4, Theorem 0.2] the global cut point of ∂(Γ, H)
point. By [3, Theorem 1.2] Γ admits a non-trivial peripheral splitting with
b
respect to H).
The edge groups in this splitting are automatically virtually
b and
cyclic, since each edge meets a vertex with vertex group conjugate into H,
b
the splitting is automatically relative to H: in fact it is relative to H.
4.3.2

Boundaries with cut pairs

In the absence of cut points, the existence of a relative splitting is reflected
in the existence of cut pairs in the boundary. In the absolute case, recall the
following theorem of [8].
Theorem 4.4. [8, Theorem 6.2] Let Γ be a one-ended hyperbolic group such
that ∂(Γ, ∅) contains a cut pair and is not homeomorphic to S 1 . Then Γ admits
a non-trivial splitting over a virtually cyclic subgroup.
We require a relative version of this theorem. We only require such a result
in the case when Γ arises as a vertex group in a splitting of a larger group
26

over virtually cyclic subgroups, and H is the collection of edge groups incident
at that vertex. In this section we show that in this simple case the relative
result follows from Theorem 4.4, and one can avoid R-trees machinery. For a
discussion in greater generality, see [21].
Proposition 4.5. Let v be a vertex in a minimal Γ-tree T with virtually cyclic
edge groups where Γ is hyperbolic and one-ended. Let Inc v be a set of representatives of Γv -conjugacy classes of stabilisers of edges in T incident at v.
Suppose that ∂(Γv , Inc v) is not a single point, does not contain a cut point and
is not homeomorphic to a circle but does contain a cut pair. Then Γv admits a
non-trivial splitting over virtually cyclic subgroups of Γv relative to Inc v.
First we need the following lemma. Recall that for a vertex v in a Γ-tree,
we defined Inc v to be a set of conjugacy class representatives of the stabilisers
[v be the set of maximal
of the edges of the Γ-tree incident at v, and let Inc
virtually cyclic subgroups of Γv that contain the elements of Inc v.
Lemma 4.6. Let f : T1 → T2 be an equivariant map of Γ-trees with virtually
infinite cyclic edge stabilisers such that the action of Γ on T1 is cocompact and
the action of Γ on T2 is minimal. (This means that there is no proper Γ[v) is not a
invariant subtree of T2 .) Let v be a vertex of T2 such that ∂(Γv , Inc
single point, is connected and does not contain a cut point. Then the action of
Γv on T1 fixes a component of f −1 (v).
Proof. First we show that there is a vertex w ∈ T1 such that Γw ∩ Γv is nonelementary. If this is not the case then the stabiliser of each edge of T1 with
respect to the action of Γv on T1 is either finite or commensurable with the
stabilisers of its end points. Therefore the action induces a splitting of Γv with
finite edge groups and virtually cyclic vertex groups. By minimality of the
action of Γ on T2 each edge e incident at v is f (e0 ) for some edge e0 of T1 , and
then Γe0 is a finite index subgroup of Γe , since each is virtually infinite cyclic.
ce is elliptic, and the splitting is relative to Inc
[v. But ∂(Γv , Inc
[v)
In particular, Γ
was assumed to be connected and not a single point, which is a contradiction.
Then f (w) = v, otherwise any edge separating f (w) from v in T2 has nonelementary stabiliser. Let S be the component of f −1 (v) containing w. We now
show that any other vertex w0 of T1 such that Γw0 ∩ Γv is non-elementary is also
in S. Suppose that e is an edge of T1 that is not in f −1 (v). As in Section 1
of [8] there exists a partition of ∂(Γ, ∅) − ΛΓe as U1 t U2 . The intersection of
Γe with Γv is either finite or commensurable with a conjugate of an element
[v, so the images of U1 ∩ ΛΓv and U2 ∩ ΛΓv under the projection map
of Inc
[v) cover all but at most a point of ∂(Γ, Inc
[v). These sets are
ΛΓv → ∂(Γ, Inc
disjoint, so one must be empty, say U2 . But ΛΓw and ΛΓw0 each contain more
than two points, so must both be contained in U1 ∪ ΛΓe . This implies that w
and w0 are on the same side of e.
Therefore the action of Γv on T1 fixes S, for any element of Γv must send w
to a vertex of S.
Proof of Proposition 4.5. Let Σ be Bowditch’s JSJ tree for Γ. Σ is then elliptic
b and maps
with respect to T , so by [23, Proposition 2.2] there exists a Γ-tree Σ
b
b
p : Σ → Σ and f : Σ → T such that:

27

b to
1. p is a collapse map. (i.e. a map given by collapsing some edges of Σ
points.)
2. For w ∈ Σ, the restriction of f to p−1 (w) is injective.
b be the component of f −1 (v) fixed by the action of Γv constructed
Let S ⊂ Σ
in Lemma 4.6. Suppose that a vertex w of S is fixed by the Γv -action.
b that is adjacent to but not contained in S then Γe ≤ Γf (e)
If e is any edge of Σ
and the subgroup is necessarily of finite index. Conversely the stabiliser of any
edge incident at v contains the stabiliser of an edge adjacent to S at finite
index. The stabiliser of any edge adjacent to S is then commensurable with
[
the stabiliser of an edge incident at w, and vice versa. Therefore ∂(Γv , Inc
w) is
[v). We assumed that ∂(Γv , Inc
[v) was neither a point
homeomorphic to ∂(Γv , Inc
nor homeomorphic to a circle, so pw is not in V1 (Σ) or V2 (Σ), and is therefore
in V3 (Σ).
[v) and choose preimages x
Let x and y be points in ∂(Γv , Inc
e and ye in
∂(Γv , ∅), which we identify with ΛΓv ⊂ ∂(Γ, ∅). The set of components of
[v) − {x, y} is in bijection with the set of those components of ∂(Γ, ∅) −
∂(Γv , Inc
{e
x, ye} that meet ΛΓv .
[v), so at least two comSuppose then that {x, y} is a cut pair in ∂(Γv , Inc
ponents of ∂(Γ, ∅) − {e
x, ye} meet ΛΓv .
Then by Theorem 4.4 there is a type 1 or type 2 vertex u of Σ such that
ΛΓu contains {e
x, ye}. Then {e
x, ye} = ΛΓu ∩ ΛΓv , so {e
x, ye} is the limit set of
[v) is a single point, which
an edge incident at v. Therefore {x, y} ⊂ ∂(Γv , Inc
[v) was assumed not to contain a cut point.
is a contradiction because ∂(Γv , Inc
Hence the action of Γv on S does not fix any vertex and therefore gives rise to
a non-trivial splitting of Γv relative to Inc v.

4.3.3

Boundaries without cut points or pairs

Our description of the relationship between the existence of splittings and the
topology of the boundary is completed by the following proposition, which serves
as a converse to Propositions 4.3 and 4.5.
Proposition 4.7. Let Γ be a hyperbolic group and let H be a finite set of
b is connected. Suppose that Γ
virtually cyclic subgroups of Γ such that ∂(Γ, H)
admits a non-trivial splitting over a virtually cyclic subgroup relative to H. Then
b contains a cut point or pair.
∂(Γ, H)
Proof. Let T be the Γ-tree associated to such a non-trivial splitting. Without
loss of generality assume that the action of Γ on T is minimal. Let e be any
edge in T . Let T1 and T2 be the two components of the complement of the
interior of e in T . Then as in the proof of Lemma 4.6 we obtain a partition of
∂(Γ, ∅) − ΛΓe as U1 t U2 where Ui are open sets given by
[
Ui = ∂Ti ∪
(ΛΓw − ΛΓe )
w∈Ti

If a subgroup H of Γ is in H, H ≤ Γw for some vertex w ∈ Σ and either
ΛH = ΛΓe or ΛH ∩ ΛΓe = ∅. In the latter case either ΛH ⊂ U1 or ΛH ⊂ U2 .
28

b be the quotient projection of Lemma 1.15. It follows
Let π : ∂(Γ, ∅) → ∂(Γ, H)
b
that the images of U1 and U2 under π in the complement of π(ΛΓe ) in ∂(Γ, H)
are disjoint open sets; they are non-empty by the minimality of the action of
b
Γ on T . The image of ΛΓe is either one or two points, and therefore ∂(Γ, H)
contains a cut point or pair.

4.4

Virtually cyclic subgroups and finding splittings

We will need the following lemma, which allows us to do various computations
related to virtually cyclic subgroups of hyperbolic groups.
Lemma 4.8. [15, Lemma 2.8] There is an algorithm that, when given a presentation for a hyperbolic group Γ and a finite subset S ⊂ Γ, returns an answer
to the question “is hSi ≤ Γ virtually cyclic?” If the answer is “yes” then the
algorithm also determines
1. the (unique) maximal finite normal subgroup of hSi,
2. a presentation for hSi,
3. whether hSi is of type Z or D∞ . (Recall that we say that a virtually cyclic
group of type Z (respectively D∞ ) if it surjects onto Z (respectively D∞ ).)
4. a generating set for the maximal virtually cyclic subgroup of Γ containing
hSi.
The proof of this lemma in [15] uses Makanin’s algorithm for solving equations in hyperbolic groups. We modify that part of the argument to use only
elementary methods in keeping with the themes of this paper.
Proof. We give an alternative method to determine whether or not hSi is virtually cyclic and to produce a maximal finite normal subgroup of hSi in the
case that it is; the rest of the argument can be copied verbatim from [15]. First
compute δ with respect to which Γ is δ-hyperbolic.
Use the algorithm of [26, Proposition 4] to search for a constant K with
respect to which hSi is K-quasi-convex in Γ. This algorithm finds such a constant if it exists and does not terminate of hSi is not quasi-convex; note that if
hSi is virtually cyclic then it is guaranteed to be quasi-convex. If the algorithm
terminates use K and δ to compute δ 0 such that hSi is δ 0 -hyperbolic. Then all
finite subgroups of hSi can be conjugated into a ball of radius at most 4δ 0 + 2
with respect to the word metric in hSi, so all finite normal subgroups of S can
be computed using a solution to the word and conjugacy problems in Γ. Once
this is computed the algorithm of [15] can be used to determine whether or not
hSi is virtually cyclic.
In parallel, search for a pair of elements g and h in hSi such that [g 2 , h2 ] has
infinite order. This can be checked since the order of an element of Γ of finite
order is bounded above by the number of elements of Γ in the ball of radius
4δ + 2.
If hSi is not quasi-convex then it contains a free group on two generators, so
a pair (g, h) as in the previous paragraph certainly exists. Conversely, if such a
pair exists then hSi cannot be virtually cyclic, since any virtually cyclic group
contains a subgroup of index two that surjects onto Z with finite kernel.
29

Lemma 4.9. There is an algorithm that takes as input a presentation for a
hyperbolic group Γ and a collection H of peripheral subgroups and either returns
the graph of groups associated to a non-trivial splitting of Γ relative to H over
virtually cyclic subgroups or does not terminate if no such splitting exists.
Proof. Suppose that Γ admits a proper splitting relative to H as an amalgamated product over a virtually cyclic subgroup; the case of an HNN extension
is similar. Then Γ admits a presentation that makes this splitting explicit in the
following sense. There are finite disjoint symmetric sets of symbols S1 , S2 and
S3 , finite subsets R1 , R2 and R3 of the free monoids S1? , S2? and S3? respectively,
and maps ι1 and ι2 from S3? to S1? and S2? respectively, such that Γ admits an
isomorphism to the group |P| with presentation P of the form
hS1 ∪ S2 ∪ S3 |R1 ∪ R2 ∪ R3 ∪ {s−1 ι1 (s), s−1 ι2 (s) : s ∈ S3 }i
where {ι1 (r)|r ∈ R3 } ⊂ R1 and {ι2 (r)|r ∈ R3 } ⊂ R2 . This ensures that ι1 and
ι2 induce group homomorphisms from hS3 |R3 i to hS1 |R1 i and hS2 |R2 i, which
we shall denote b
ι1 and b
ι2 . Let b
ι be the induced map from hS3 |R3 i to Γ. Then
the assumptions on the nature of the splitting give the following conditions:
1. that hS3 |R3 i be virtually cyclic,
2. that b
ι1 and b
ι2 be injective,
3. that b
ι1 and b
ι2 not be surjective and
4. that for each H ∈ H with generating set SH there exists gH in Γ such that
−1
either S1 or S2 contains the image of gH SH gH
under the isomorphism
from Γ to |P|.
We show that there is an algorithm that finds such a presentation for Γ if it
exists. Using Tietze transformations, there is an algorithm that enumerates all
presentations of Γ and for each presentation gives an explicit isomorphism from
Γ to the realisation of that presentation; therefore it is sufficient to show that
each of the four conditions above can be checked algorithmically.
The first condition can be checked using the first part of the algorithm of
Lemma 4.8.
b
ι1 and b
ι2 are both injective if and only if b
ι is injective: one direction is trivial,
the other is a consequence of the normal form theorem for the amalgamated
product. To check this condition, compute the maximal finite normal subgroup
of hS3 |R3 i and check the triviality of the image under b
ι of each of these elements.
Then find an element of hS3 |R3 i of infinite order and check whether or not the
image under b
ι of this element has infinite order.
To check the surjectivity of b
ι1 first check whether or not hS1 i is virtually
cyclic. If it is, check whether or not the maximal finite normal subgroup of
Im b
ι1 is equal to the maximal finite normal subgroup of hS1 i. If it is, next
check whether or not hS1 i and hS3 i are either both of Z-type or both of D∞
type. If they are both of the same type, pass to an index 2 subgroup of each
if necessary to ensure that they are both of Z type, then check whether or not
the composition of b
ι1 with the natural surjection to Z is surjective. If it is then
b
ι1 is surjective; if any of these tests produced the opposite answer then b
ι1 is not
surjective. Repeat this process for b
ι2 .
30

No

‡(n, 0) for
some n?

Start

No

Splitting

Yes

Yes

Cut
point?

Virtually
cyclic?

No
No

Yes
No
splitting

No

Yes

Cut pair?

Small
orbifold?
Yes

Figure 1: The decision process in the algorithm of Proposition 4.11.
The final condition can be checked using a solution to the simultaneous
conjugacy problem in Γ.
The existence of such a presentation for Γ guarantees that Γ splits nontrivially as an internal amalgamated product
Γ∼
= hS1 |R1 i ∗hS3 |R3 i hS2 |R2 i.
This splitting is over a virtually cyclic subgroup of Γ and is relative to H.

4.5

Computing a maximal splitting

We will need to be able to determine algorithmically whether or not the boundary of the given hyperbolic group is homeomorphic to a circle. This is achieved
using the algorithm of Corollary 2.7 and a theorem from point-set topology,
which we note here.
Theorem 4.10. [35, II.2.13] Any separable, connected, locally connected space
containing more than one point that is without a cut point and in which every
pair is a cut pair is homeomorphic to S 1 .
Proposition 4.11. There is an algorithm that takes as input a presentation for
a hyperbolic group Γ with a collection H of virtually cyclic subgroups such that
b is connected and Γ appears as the stabiliser of some vertex in the action
∂(Γ, H)
of a hyperbolic group on a tree and H is a set of conjugacy class representatives
of incident edge groups and returns the answer to the question “does Γ split
non-trivially over a virtually cyclic subgroup relative to H?”

31

Proof. Let the given group be Γ and the peripheral structure be H. First check
whether or not Γ is virtually cyclic. If it is then Γ does not split properly over
b then ∂(Γ, H)
b contains
a virtually cyclic subgroup. If it is not then compute H;
more than a single point and the results of this section can be applied.
b
Next compute δ such that the cusped space X associated to the pair (Γ, H)
is δ-hyperbolic. Search for a non-trivial splitting of Γ relative to H using
Lemma 4.9 and, in parallel, search for n such that ‡n holds in X; one of these
processes must terminate by Proposition 1.16 and Proposition 4.3.
If a splitting is found then Γ does split non-trivially over a virtually cyclic
subgroup relative to H, and the algorithm can return “yes”. If X satisfies ‡n
b contains
then use the algorithm of Corollary 2.4 to check whether or not ∂(Γ, H)
a cut point. If it does then Γ does split properly over a virtually cyclic subgroup
by Proposition 4.3
If there is no cut point, use the algorithm of Corollary 2.4 on X to determine
b contains a cut pair; if it does not then Γ does not split relative
whether or ∂(Γ, H)
to H by Proposition 4.7.
If there is a cut pair then simultaneously run the algorithms of Lemma 4.9
and Lemma 3.7. If the former terminates then a splitting has been found; if the
latter does then no splitting exists.
Note that a subprocess of this algorithm, together with the algorithm of [20]
that determines whether or not a hyperbolic group is one-ended, provides the
algorithm promised in Theorem 0.2.
Proposition 4.12. There is an algorithm that, when given a presentation for
a hyperbolic group, computes the graph of groups associated to a splitting of that
group that is maximal for domination.
Proof. The algorithm iteratively constructs a sequence of Γ-marked graphs of
groups Gi . Let G1 consist of a single vertex with vertex group Γ. Then to obtain
Gi+1 from Gi , use Proposition 4.11 to check whether each vertex group splits
non-trivially relative to its incident edge groups. If no vertex group does split
then halt the algorithm here. If the group at a vertex v does split then find the
non-trivial graph of groups G0 with fundamental group Γv using Lemma 4.9.
Then define Gi+1 by replacing the vertex v of Gi by the graph G0 and connecting
edges corresponding to the edges of Gi incident at v to G0 in the obvious way.
This process must eventually stabilise: this follows from an accessibility
theorem [1] since the associated group actions on trees constructed are minimal
and reduced by construction. Let the corresponding Γ-trees stabilise at a Γ-tree
T.
Suppose that another Γ-tree T 0 with virtually cyclic edge stabilisers dominates T . Let v be a vertex of T . If e is an incident edge then Γe is elliptic with
respect to the action on T 0 , since it contains the stabiliser of an edge of T 0 as a
subgroup of finite index. Therefore each incident edge subgroup of Γv is elliptic
with respect to T 0 . The vertex stabiliser Γv does not split over a virtually cyclic
subgroup relative to its incident edge groups, so Γv is elliptic with respect to
T 0 . The vertex v was arbitrary, so T dominates T 0 , and so T is maximal for
domination.

32

5

JSJ Decompositions

In this section we show that three closely related types of JSJ splittings are
computable for hyperbolic groups. Fix a one-ended hyperbolic group Γ and
recall that VC is defined to be the set of all virtually cyclic subgroups of Γ, Z
is defined to be the set of all virtually cyclic subgroups of Γ with infinite centre
and Zmax is defined to be the set of subgroups of Γ in Z that are maximal for
inclusion. We consider the JSJ splittings over groups in these three sets.

5.1

Two-ended edge groups

We now prove the first part of Theorem 0.1.
Theorem 5.1. There is an algorithm that takes as input a presentation for a
one-ended hyperbolic group and returns as output the graph of groups associated
to a VC-JSJ decomposition for that group. This decomposition can be taken to
be Bowditch’s canonical decomposition.
We first prove the following lemma.
Lemma 5.2. The tree obtained from the tree associated to a maximal splitting
by collapsing each edge whose stabiliser is not universally elliptic is a VC-JSJ
tree.
Proof. Let T be the tree associated to a maximal splitting and let T 0 be the
tree obtained by collapsing each edge of T that is not universally elliptic. Then
certainly T 0 is universally elliptic, so it is sufficient to show that if Σ is another
universally elliptic Γ-tree then T 0 dominates Σ.
The tree Σ can be refined to dominate T , so there exists a map f : T → Σ.
Let v be a vertex of T 0 and let S be a component of its preimage in T . Then
f |S is constant: if an edge e in S is mapped into an edge e0 in Σ then Γe ≤ Γe0 ,
which is universally elliptic. But then the image of S in T 0 contains more than a
single vertex. Therefore Γv fixes the vertex f (S) in Σ, so is elliptic with respect
to Σ. This shows that T 0 dominates Σ.
We must now identify the edges in the tree associated to the maximal splitting that are not maximally elliptic. We make the following definitions.
Definition 5.3. An extended Möbius strip group is a virtually cyclic group of
Z type with peripheral structure consisting of a single index 2 subgroup.
Definition 5.4. We say that an edge e connecting vertices v1 and v2 of a Γ-tree
is a internal surface edge if, for each i, either Γvi is a hanging Fuchsian group
and Γe is maximal among virtually cyclic subgroups of Γvi , or Γvi is an extended
Möbius strip group and Γe ≤ Γvi is the peripheral subgroup of Γvi .
Lemma 5.5. If T is reduced (that is, no proper collapse of T dominates T )
then the edges of T that are not universally elliptic are precisely the internal
surface edges.
Proof. Let T 0 be the tree obtained by collapsing each edge of T that is not
universally elliptic as in Lemma 5.2, so T 0 is a JSJ tree and there is a collapse
map from T to T 0 . The edges of T that are not universally elliptic are precisely
33

those edges that are mapped to flexible vertices of T 0 under the collapse map;
by [23, Theorem 6.2] all flexible vertices of T 0 are hanging Fuchsian vertices.
Any splitting of a hanging Fuchsian group is dual to a family of curves on
the associated orbifold, so any edge in such a splitting is an internal surface
edge, so all edges that are not universally elliptic are internal surface edges.
Conversely, let e be an internal surface edge. Let T 0 be the tree obtained
by collapsing each edge in the orbit of e; let v be the vertex of T 0 in the image
of e. Then T is obtained from T 0 by refining at v. The tree T was assumed to
be reduced and v is a hanging Fuchsian vertex so this refinement is dual to an
essential simple closed curve ` on the associated orbifold Q. Then Q contains
another essential simple closed curve `0 that is not homotopic to a curve disjoint
from `. Refine T 0 at v dual to `0 to obtain a tree T 00 ; then Γe is not elliptic with
respect to T 00 .
We now have sufficient tools to prove the computability of a VC-JSJ for a
given hyperbolic group G. In [8], Bowditch defines a canonical JSJ in the class
of all VC-JSJs of a given hyperbolic group. In the language of [23] this is the
decomposition corresponding to the tree of cylinders of any other VC-JSJ.
Definition 5.6. Let T be a VC-tree. Define the commensurability equivalence
relation ∼ on VC by letting A ∼ B if and only if A and B lie in the same maximal
virtually cyclic subgroup of Γ. Also denote by ∼ the equivalence relation on the
set of edges of T defined by letting e ∼ e0 if and only if Γe ∼ Γe0 . A cylinder is
a subset Y ⊂ T that is the union of all edges in a ∼-equivalence class.
Definition 5.7. Let T be a VC-tree. The corresponding tree of cylinders Tc is
a bipartite tree with vertex set V1 t V2 , where V1 is the set of vertices of T that
lie in at least two cylinders and V2 is the set of cylinders in T . A vertex v ∈ V1
is connected by an edge to Y ∈ V2 if and only if v ∈ Y .
Proof of Theorem 5.1. First compute a maximal splitting of the group over virtually cyclic subgroups by Theorem 4.12. Let T be the associated tree. By
construction T is reduced; in any case, T can easily be made reduced using the
processes of Lemma 4.8. For each edge e connecting vertices v1 and v2 of the
graph of groups T /Γ determine whether Γe is maximal in Γ using the algorithm
of Lemma 4.8 and whether the two vertex groups Γv1 and Γv2 have circular
boundary relative to their incident edge groups by Theorem 0.2. Check also
whether each of Γv1 and Γv2 is virtually cyclic of Z-type, and, if it is, whether
or not Γe has index 2 in that group. One of these possibilities is the case if and
only if e is not universally elliptic by Lemma 5.5; collapse all edges where this
is the case.
Bowditch’s canonical decomposition is the graph of cylinders of the decomposition obtained in this way. The operation of replacing a decomposition with
the decomposition associated to its tree of cylinders can be done algorithmically
using 4.8. This is result the content of [15, Lemma 2.34]; note that while the
result is stated for a Z-tree, replacing this with a VC-tree makes no difference
to the proof.

5.2

Z edge groups

We now prove the second part of Theorem 0.1.

34

Theorem 5.8. There is an algorithm that takes as input a presentation for
a one-ended hyperbolic group and returns the graph of groups associated to a
Z-JSJ decomposition for that group.
In [15] it is shown that the Z-JSJ decomposition is closely related to the
VC-JSJ: a Z-JSJ tree can be obtained from a VC-JSJ tree T by first refining
T by applying the so-called mirrors splitting to each hanging Fuchsian vertex
group and then collapsing each edge with stabiliser of dihedral type. The second
of these processes can be done algorithmically using the part of the algorithm
of Lemma 4.8 that determines whether or not a given virtually cyclic group
is of dihedral type. Therefore we must now show that the mirrors splitting is
computable.
Recall the definition of the mirrors splitting of the fundamental group of a
compact 2-dimensional orbifold Q from [15].
Definition 5.9. Let N be a regular neighbourhood of the union of the mirrors
and D∞ -boundary components of Q that does not contain any cone point of Q.
If Q − N is an annulus or a disc with at most one cone point then the mirrors
splitting of π1 Q is defined to be trivial; otherwise it is the splitting obtained by
cutting Q along each component of ∂N .
If the mirrors splitting is non-trivial then the graph of groups associated to
the splitting is a star; the group at the central vertex is the fundamental group
of an orbifold with no mirrors and the group at each leaf is the fundamental
group of an orbifold with no cone points and underlying surface an annulus, one
of whose topological boundary components is a circular orbifold boundary component and the other a union of interval boundary components and at least one
mirror. If Γ is any hyperbolic group with a collection H of virtually cyclic subb is homeomorphic to a circle then the mirrors splitting
groups such that ∂(Γ, H)
of Γ relative to H is defined to be the splitting induced by the mirrors splitting of
the quotient Γ by a maximal finite normal subgroup of Γ as in Proposition 3.3.
Lemma 5.10. The mirrors splitting of a hyperbolic group Γ with a set H of
b is homeomorphic to a circle is comvirtually cyclic subgroups such that ∂(Γ, H)
putable.
Proof. Using Proposition 3.3 it is enough to show that the mirrors splitting is
computable in the case where Γ is bounded Fuchsian and H is the a collection of
representatives of peripheral subgroups of Γ. To do this we enumerate all mirrors
splittings: for each non-negative integer k enumerate all fundamental groups of
compact orbifolds without mirrors and with at least k boundary components and
all k-tuples of fundamental groups of orbifolds homeomorphic to an annulus with
no cone points and such that one topological boundary component of the orbifold
is a circular orbifold boundary component. In each case form the graph of groups
in which the underlying graph is a k-pointed star, the group at the central vertex
is the fundamental group of the orbifold without mirrors, the group at each leaf
is the fundamental group of an orbifold homeomorphic to an annulus and the
group at each edge is infinite cyclic and is identified with the fundamental group
of a circular orbifold boundary component of each of the orbifolds associated
to the end points of that edge. Compute the fundamental group of each such
graph of groups and record also the peripheral structure consisting of conjugacy

35

class representatives of the fundamental groups of components of the orbifold
boundary of the orbifold.
Also enumerate all groups with trivial mirrors splitting, i.e. fundamental
groups of orbifolds homeomorphic as topological spaces to a disc with at most
one cone point, or homeomorphic to an annulus with no cone points and such
that one topological boundary component is a circular orbifold boundary component.
In parallel enumerate all homomorphisms from the fundamental groups of
these graphs of groups to Γ and all homomorphisms from Γ to the fundamental
groups of these graphs of groups. Some such pair of homomorphisms is an
inverse pair that preserves the peripheral structure up to conjugacy. On finding
this pair the algorithm returns the associated mirrors splitting.

5.3

Zmax edge groups

In [15] it is shown that the Zmax -JSJ decomposition can be obtained from a
Z-JSJ decomposition by performing the so-called Zmax -fold. We note that this
can be done algorithmically, which completes the proof of the final part of
Theorem 0.1, which we restate here as Theorem 5.11.
Theorem 5.11. There is an algorithm that takes as input a presentation for
a one-ended hyperbolic group and outputs the graph of groups associated to a
Zmax -JSJ decomposition for that group.
Lemma 5.12. There is an algorithm that takes as input a graph of groups
decomposition of a hyperbolic group Γ over virtually cyclic subgroups and returns
the graph of groups associated to the Zmax -fold of the associated Γ-tree.
Proof. This can be done by iterating some simple folds described in [15]. We
describe this fold at the level of the tree T . Take some edge e in T such that
the maximal subgroup Γ̂e of Γ containing Γe is a subgroup of Γo(e) where o(e)
is the origin of e. Then take the quotient of T by the Γ-equivariant equivalence
relation generated by e ∼ Γ̂e · e. Note that this does not change the underlying
graph of the associated graph of groups.
At the level of the graph of groups this fold is achieved by taking an edge e
in the graph such that Γ̂e is a subgroup of Γo(e) , replacing the group at the edge
e by Γ̂e and replacing the group at the terminal vertex t(e) of e by hΓ̂e , Γt(e) i.
Repeat this process until there is no edge e such that Γe 6= Γ̂e .

References
[1] Mladen Bestvina and Mark Feighn. Bounding the complexity of simplicial
group actions on trees. Invent. Math., 103(3):449–469, 1991.
[2] Mladen Bestvina and Geoffrey Mess. The boundary of negatively curved
groups. J. Amer. Math. Soc., 4(3):469–481, 1991.
[3] B. H. Bowditch. Boundaries of geometrically finite groups. Math. Z.,
230(3):509–527, 1999.
[4] B. H. Bowditch. Connectedness properties of limit sets. Trans. Amer.
Math. Soc., 351(9):3673–3686, 1999.
36

[5] B. H. Bowditch. Convergence groups and configuration spaces. In Geometric group theory down under (Canberra, 1996), pages 23–54. de Gruyter,
Berlin, 1999.
[6] B. H. Bowditch. Peripheral splittings of groups. Trans. Amer. Math. Soc.,
353(10):4057–4082, 2001.
[7] B. H. Bowditch. Relatively hyperbolic groups. Internat. J. Algebra Comput., 22(3):1250016, 66, 2012.
[8] Brian H. Bowditch. Cut points and canonical splittings of hyperbolic
groups. Acta Math., 180(2):145–186, 1998.
[9] Martin R. Bridson and André Haefliger. Metric spaces of non-positive curvature, volume 319 of Grundlehren der Mathematischen Wissenschaften
[Fundamental Principles of Mathematical Sciences]. Springer-Verlag,
Berlin, 1999.
[10] Christopher H. Cashen and Nataša Macura. Line patterns in free groups.
Geom. Topol., 15(3):1419–1475, 2011.
[11] Andrew Casson and Douglas Jungreis. Convergence groups and Seifert
fibered 3-manifolds. Invent. Math., 118(3):441–456, 1994.
[12] F. Dahmani and N. Touikan. Isomorphisms using Dehn fillings: the splitting case. ArXiv e-prints, November 2013, 1311.3937.
[13] François Dahmani. Finding relative hyperbolic structures. Bull. Lond.
Math. Soc., 40(3):395–404, 2008.
[14] François Dahmani and Daniel Groves. Detecting free splittings in relatively
hyperbolic groups. Trans. Amer. Math. Soc., 360(12):6303–6318, 2008.
[15] François Dahmani and Vincent Guirardel. The isomorphism problem for
all hyperbolic groups. Geom. Funct. Anal., 21(2):223–300, 2011.
[16] M. J. Dunwoody and M. E. Sageev. JSJ-splittings for finitely presented
groups over slender groups. Invent. Math., 135(1):25–44, 1999.
[17] J. Fox Manning. The Bowditch boundary of (G, H) when G is hyperbolic.
ArXiv e-prints, April 2015, 1504.03630.
[18] K. Fujiwara and P. Papasoglu. JSJ-decompositions of finitely presented
groups and complexes of groups. Geom. Funct. Anal., 16(1):70–125, 2006.
[19] David Gabai. Convergence groups are Fuchsian groups. Ann. of Math. (2),
136(3):447–510, 1992.
[20] V. Gerasimov. Detecting connectedness of the boundary of a hyperbolic
group. Unpublished.
[21] Bradley W. Groff. Quasi-isometries, boundaries and JSJ-decompositions
of relatively hyperbolic groups. J. Topol. Anal., 5(4):451–475, 2013.
[22] Daniel Groves and Jason Fox Manning. Dehn filling in relatively hyperbolic
groups. Israel J. Math., 168:317–429, 2008.
37

[23] V. Guirardel and G. Levitt. JSJ decompositions of groups. ArXiv e-prints,
February 2016, 1602.05139.
[24] William Jaco and Peter B. Shalen. Seifert fibered spaces in 3-manifolds.
In Geometric topology (Proc. Georgia Topology Conf., Athens, Ga., 1977),
pages 91–99. Academic Press, New York-London, 1979.
[25] Klaus Johannson. Homotopy equivalences of 3-manifolds with boundaries,
volume 761 of Lecture Notes in Mathematics. Springer, Berlin, 1979.
[26] Ilya Kapovich. Detecting quasiconvexity: algorithmic aspects. In Geometric and computational perspectives on infinite groups (Minneapolis, MN and
New Brunswick, NJ, 1994), volume 25 of DIMACS Ser. Discrete Math.
Theoret. Comput. Sci., pages 91–99. Amer. Math. Soc., Providence, RI,
1996.
[27] Gilbert Levitt. Automorphisms of hyperbolic groups and graphs of groups.
Geom. Dedicata, 114:49–70, 2005.
[28] C. F. Miller, III, Walter D. Neumann, and G. A. Swarup. Some examples
of hyperbolic groups. In Geometric group theory down under (Canberra,
1996), pages 195–202. de Gruyter, Berlin, 1999.
[29] Frédéric Paulin. Outer automorphisms of hyperbolic groups and small actions on R-trees. In Arboreal group theory (Berkeley, CA, 1988), volume 19
of Math. Sci. Res. Inst. Publ., pages 331–343. Springer, New York, 1991.
[30] E. Rips and Z. Sela. Cyclic splittings of finitely presented groups and the
canonical JSJ decomposition. Ann. of Math. (2), 146(1):53–109, 1997.
[31] Peter Scott. The geometries of 3-manifolds. Bull. London Math. Soc.,
15(5):401–487, 1983.
[32] Z. Sela. Structure and rigidity in (Gromov) hyperbolic groups and discrete
groups in rank 1 Lie groups. II. Geom. Funct. Anal., 7(3):561–593, 1997.
[33] N. W. M. Touikan. Detecting geometric splittings in finitely presented
groups. ArXiv e-prints, June 2009, 0906.3902.
[34] Pekka Tukia. Homeomorphic conjugates of Fuchsian groups. J. Reine
Angew. Math., 391:1–54, 1988.
[35] Raymond Louis Wilder. Topology of Manifolds. American Mathematical
Society Colloquium Publications, vol. 32. American Mathematical Society,
New York, N. Y., 1949.

38

