{'fraction_non_alphanumeric': 0.039504950495049505, 'fraction_numerical': 0.008292079207920793, 'mean_word_length': 3.7482517482517483, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quasi-isometries Between Tubular Groups

We give a method of constructing maps between tubular groups inductively according to a set of strategies. This map will be a quasi-isometry exactly when the set of strategies is consistent. Conversely, if there exists a quasi-isometry between tubular groups, then there is a consistent set of strategies for them. There is an algorithm that will in finite time either produce a consistent set of strategies or decide that such a set does not exist. Consequently, this algorithm decides whether or not the groups are quasi-isometric.


Introduction
One line of attack in Gromov's program to classify finitely generated groups up to quasi-isometry has been to study splittings of groups. Given a splitting of a group G into a graph of groups, one would like to know whether there is a similar splitting for a finitely generated group H quasi-isometric to G, and what constraints such splittings impose upon quasi-isometries between the groups.
A result of this type applies when G and H are accessible groups. Paposoglu and Whyte showed that G and H are quasi-isometric if and only if they have the same number of ends and if, in terminal splittings over finite subgroups, they have the same sets of quasi-isometry classes of one ended vertex groups [10]. In terms of the Bass-Serre trees for such groups, this is a local restriction.
When edge groups are infinite there may be large scale restrictions as well. Consider, for example, graphs of groups where all the local groups are infinite cyclic, such as the Baumslag-Solitar groups. Here there are no obvious local restrictions; all the vertex spaces are quasi-isometric to each other. However, crossing an edge space contributes a height change. Quasi-isometries between graphs of Z's must induce coarsely height preserving quasi-isometries of the corresponding Bass-Serre trees [14].
Perhaps the next most complicated situation to consider would be graphs of groups with infinite cyclic edge groups and vertex groups free abelian of rank two. Such a group can be thought of as the fundamental group of a finite 2-complex consisting of a disjoint union of tori glued together by annuli. Martin Bridson has described such groups as "tubular".
Mosher, Sageev, and Whyte prove splitting rigidity results for graphs of coarse Poincaré duality groups under some additional hypotheses [8], [9]. We define a class of tubular groups that satisfy these hypotheses. Such splittings are quasiisometrically rigid. Furthermore, the patterns of attachment of edge groups to vertex groups are quasi-isometry invariants of the groups. These edge patterns give local quasi-isometry restrictions, and height change gives a large scale restriction, similar to the graph of Z's example.
We will show that we can cover the Bass-Serre tree of a tubular group by a collection of infinite subtrees, called P-sets, that intersect pairwise in at most a single vertex. We organize the P-sets into a tree of P-sets, which is essentially the nerve of the aforementioned cover. The P-sets are similar to the Bass-Serre trees of Baumslag-Solitar groups, and we can use similar methods to construct quasi-isometries between P-set spaces. To construct quasi-isometries of tubular groups we will need to coordinate the quasi-isometries on each P-set space so that they piece together in such a way as to satisfy the local edge-to-vertex pattern rigidity and global height change restrictions.
To accomplish this, we define sets of strategies for inductively building quasiisometries in a way that will satisfy the local restrictions given by edge pattern rigidity. We give consistency criteria for such a set of strategies that determine whether the large scale restrictions on height change are satisfied. Theorem 4.5 shows that there is an algorithm that in finite time will either produce a consistent set of strategies or decide that no such set exists.
We prove a number of results that can be summarized as: Theorem. The following are equivalent: 1. The tubular groups G 1 and G 2 are quasi-isometric.
2. There exists an allowable isomorphism between the trees of P-sets of G 1 and G 2 .
3. There exists a consistent set of strategies for G 1 and G 2 .
Combining these results with Theorem 4.5, we get the main result of this paper: Main Theorem. There is an algorithm that will take graph of groups decompositions of two tubular groups and in finite time decide whether or not the groups are quasi-isometric.

Previous Examples of Tubular Groups
Examples of tubular groups have appeared in the literature in various guises.
The fundamental group of the Torus Complexes of Croke and Kleiner [7] is an example of a tubular group. These Torus Complexes provided examples of finite, non-positively curved, homeomorphic 2-complexes whose universal covers have non-homeomorphic ideal boundaries.
Right-Angled Artin groups whose defining graphs are trees of diameter at least three are tubular groups. Such groups are also graph-manifold groups and have been shown to be quasi-isometric to each other by Behrstock and Neumann as a special case of their quasi-isometry classification of graph-manifold groups [1]. This result is recovered as Corollary 5.2 Examples of tubular groups were used in work of Brady and Bridson [2], as well as Brady, Bridson, Forester, and Shankar [3], to show that the isoperimetric spectrum is dense in [2, ∞) and that Q ∩ [2, ∞) ⊂ IP , respectively. In the latter work these examples were termed "snowflake groups".
Wise's group W = a, b, x, y | [a, b] = 1, x −1 ax = (ab) 2 , y −1 by = (ab) 2 is a tubular group that is non-Hopfian and CAT(0) [15]. It is not known if this group is automatic. Resolving this question would either provide an example of a non-Hopfian automatic group or a non-automatic CAT(0) group.

Acknowledgements
This paper is based on a thesis [6] submitted in partial fulfillment of the requirements for the doctoral degree at the Graduate College of the University of Illinois at Chicago, under the supervision of Kevin Whyte. Additional work was conducted during MSRI's Geometric Group Theory Program.

Preliminaries
This section contains standard definitions and constructions. Notation will most closely resemble that of Mosher, Sageev, and Whyte [9].

Coarse Geometry
Let (X, d X ) and (Y, d Y ) be metric spaces, and let A, B ⊂ X. The closed rneighborhood of A in X is denoted N r (A). The set A is coarsely contained in B, A c ⊂ B, if ∃r such that A ⊂ N r (B). Subsets A and B are coarsely equivalent, A γ, choose K γ to be a pointed, connected, compact CW-complex, with a map π 1 (K γ ) → G γ . This map should be an isomorphism if γ ∈ VΓ , and an epimorphism if γ ∈ EΓ . For each endpoint η of Γ, choose an edge map, a pointed CW-map f η : K e(η) → K v(η) , such that the induced map on fundamental groups agrees with the edge injection. Now, let K be the finite CW-complex obtained from the disjoint union v∈VΓ K v e∈EΓ K e × [0, 1] by using f (e,i) to glue K e×{i} to K v(e,i) for each endpoint (e, i). The fundamental group π 1 (K) is well defined, up to isomorphism, and, by van Kampen's Theorem, is isomorphic to G. Consider the universal cover X =K, with covering map p and metric lifted from K. The group G acts properly discontinuously, cocompactly and isometrically by deck transformations on X, so G and X are quasi-isometric by theSvarc-Milnor Lemma [5]. Thus, X serves as a geometric model for G. For questions of the coarse geometry of G, it is sufficient to study X.
The space X can be decomposed into path connected lifts of the local spaces K γ , and the action of G on X respects this decomposition. Let DΓ = q(X) be the quotient space of the decomposition. The quotient is a tree on which G acts without edge inversion, and DΓ is G-equivariantly isomorphic to the Bass-Serre Tree of Γ. We use the notation DΓ because the tree is the "development" of Γ. Call X the Bass-Serre Complex, and X q → DΓ the Bass-Serre tree of spaces for Γ.
For v ∈ VDΓ , X v = q −1 (v) is called a vertex space, and VX = v∈VDΓ X v is the set of vertex spaces. The set of vertex spaces is 1 2 -coarsely dense in X. For e ∈ EDΓ , X e = q −1 (midpoint of e) is called an edge space.
For t ∈ DΓ , Stab G (t) = Stab G (X t ). The group Stab G (t) is conjugate in G to G p(t) , and Stab G (t) acts on X t as the deck transformation group of the covering map X t → K p(t) .

Definition of Tubular Group
The motivating examples of tubular groups are graphs of groups with edge groups Z and vertex groups Z 2 . However, this description is not sufficient to give a quasiisometrically closed class of groups. Definition 3.1. A tubular group is the fundamental group of a finite, connected graph of groups satisfying the following conditions: 1. Every edge group is finitely generated and quasi-isometric to Z.
2. Every vertex group is finitely generated and quasi-isometric to either Z or Z 2 .
3. There is at least one vertex group quasi-isometric to Z 2 and at least one edge.
4. Every vertex whose local group is quasi-isometric to Z 2 satisfies the crossing graph condition. (see below) Remarks.
• Graphs of groups with all local groups quasi-isometric to Z have been classified by Whyte [14]. Conditions (3) and (4) exclude such groups from consideration.
• Suppose v ∈ VΓ with G v quasi-isometric to Z. Suppose e ∈ EΓ such that v(e, i) = v and v(e, i + 1) = v. We can assume that φ (e,i) (G e ) is a subgroup of G v of index at least two. Otherwise, the graph of groups is reducible and could be simplified without changing the fundamental group.

The Crossing Graph Condition
In a graph of groups, a depth zero vertex group is one that is not strictly coarsely contained in any other vertex group. In a tubular group, those are precisely the vertex groups quasi-isometric to Z 2 .
We define a crossing graph condition for tubular groups. Mosher, Sageev, and Whyte define a crossing graph condition in [9] that applies to more general graphs of groups. For tubular groups the two definitions are equivalent.
Definition 3.2. For each v ∈ V 0 DΓ the crossing graph for v is a graph with one vertex for each edge incident to v in DΓ . Vertices of the crossing graph corresponding to edges e and e are joined by an edge in the crossing graph if either X e and X e cross in X v or if there is a third edge e incident to v such that X e crosses both X e and X e in X v . Definition 3.3. A depth zero vertex satisfies the crossing graph condition if its crossing graph is connected.
If the vertex group is isomorphic to Z 2 the crossing graph condition is even simpler: the vertex satisfies the crossing graph condition if and only if the incident edge groups rationally span the vertex group.
The crossing graph condition fails in a tubular group only if for some depth zero vertex v, all of the incident edges have edge spaces coarsely equivalent to each other in X v .
For example, the group F 2 ×Z = a, b × c can be regarded as a graph of groups with one Z 2 vertex and one Z edge in two different ways. The Z 2 vertex group could be either a, c or b, c . Neither of these descriptions satisfy the crossing graph condition, because in each case the images of the two edge injections are the same cyclic subgroup of the vertex group. The quasi-isometry coming from the obvious isomorphism does not respect vertex spaces, it takes the vertex space corresponding to a, c to a union of edge spaces.
The crossing graph condition will prevent this sort of problem; it will ensure that a quasi-isometry of tubular groups takes depth zero vertex spaces to within bounded distance of depth zero vertex spaces. We will not give a direct proof of this statement for tubular groups, it will be a consequence of more general theorems of Mosher, Sageev, and Whyte. However, it is easy to get an idea of why this works. If a vertex satisfies the crossing graph condition then no line, l, in the vertex space can coarsely separate the vertex space in the whole tree of spaces. There will be some transverse line with an edge space attached, so we could avoid any neighborhood of l by going far out in either direction along the transverse edge line, then crossing to the other side of the edge strip. On the other side of the edge strip is a vertex space quasi-isometric to a plane, and the intersection of any neighborhood of l with this plane is bounded, so we can avoid it in the plane. If the image of a depth zero vertex space is not contained in a bounded neighborhood of some depth zero vertex space then it must cross deeply into components on opposite sides of some edge space. That edge space coarsely separates the entire tree of spaces, which means its preimage would be a line coarsely separating the vertex space in the tree of spaces, and this would be a contradiction.

Rigidity Results of Mosher-Sageev-Whyte
In this subsection we recall results of Mosher, Sageev, and Whyte [9] and apply them to tubular groups.
Given a graph of groups, Γ, with Bass-Serre tree of spaces X → T , the following hypotheses will be needed: 1. Γ is finite type, irreducible, and finite depth.
2. No depth zero raft of the Bass-Serre tree T is a line.
3. Each depth zero vertex group is coarse PD.
4. The crossing graph condition holds for each depth zero vertex of T that is a raft.
5. Each vertex and edge group of Γ is coarse finite type.
Proof. The depth zero vertices are all rafts, and these are the only depth zero rafts. We have included the crossing graph condition in the definition of tubular groups. We can assume irreducibility, as discussed in the remarks following the definition of tubular groups. Virtually abelian groups are coarse PD and coarse finite type. Finite depth means there is a bound to the length of a chain of proper coarse inclusions of vertex and edge spaces. For tubular groups there are only chains of length two.
Theorem 3.6 (Quasi-isometric Classification Theorem). [9, Theorem 1.6] Let Γ, Γ be graphs of groups satisfying (1)-(5) above. Let X → T , X → T be Bass-Serre trees of spaces for Γ, Γ , respectively. If f : X → X is a quasi-isometry then f coarsely respects vertex and edge spaces. To be precise, for any K ≥ 1, C ≥ 0 there exists a K , C quasi-isometry f # : VE(T ) → VE(T ) such that the following hold: The class of tubular groups is closed under quasi-isometry. That is, any finitely generated group quasi-isometric to a tubular group is itself a tubular group. Furthermore, any quasi-isometry between tubular groups coarsely respects vertex and edge spaces.
Note that in a tubular group, a vertex space quasi-isometric to Z 2 is not bounded Hausdorff distance from any other vertex space. Thus, we can change a quasi-isometry by a bounded amount so that it actually respects such vertex spaces.
If V ⊂ R n is a linear subspace, let P V be the set of affine subspaces of R n parallel to V . For a finite collection, F , of linear subspaces, the affine pattern induced by F , P F , is the union of the P V for V ∈ F . An affine pattern is rigid if for every K, C, R there is an R such that if f : R n → R n is a K, C quasi-isometry that R-coarsely respects each P V , then f is within R of an affine homothety.
Lemma 3.8. [9, Lemma 7.2] If F is a finite collection of linear subspaces of R n that contains n + 1 hyperplanes in general position, then F is rigid.
In particular, a collection of at least three distinct lines in the plane is rigid. Corollary 3.9. [9, Corollary 7.11] Let Γ be a graph of groups with all vertex and edge groups finitely generated abelian groups. Assume that for each depth zero, one vertex raft v in the Bass-Serre tree, the collection of edge spaces at the vertex space of v is a rigid affine pattern. Assume also that there are no line-like rafts of depth zero. If H is any finitely generated group quasi-isometric to G = π 1 (Γ), then H splits as a graph of virtually abelian groups and the quasi-isometry G → H is affine along each depth zero, one vertex raft. Moreover, the set of affine equivalence classes of edge patterns is the same for H as it is for G.

Geometric Models for Tubular Groups
Recall that an edge pattern is rigid if any quasi-isometry that respects each of the families of parallel lines is bounded distance from an affine homothety. We will choose the metrics on the vertex spaces so that rigid patterns are "symmetric". The payoff for choosing the metrics in this way will be that any quasi-isometry which respects the edge pattern (possibly permuting families of parallel lines) is bounded distance from the composition of an isometry and a homothety. As a consequence, a quasi-isometry of tubular groups restricted to a depth zero vertex space with an edge pattern consisting of at least three families of parallel lines must stretch distances by the same amount in every direction.

Affine Patterns of Lines in the Plane
Let F = {l 1 , l 2 , .., l n }, n ≥ 3, be a finite collection of distinct lines through the origin in R 2 , with the usual Euclidean metric. Two such collections, F and F , are linearly equivalent if there exists A ∈ GL 2 R such that AF = {Al i } = F . Scalar matrices in GL 2 R will preserve any such F , so we projectivise.
Let P F = {m 1 , m 2 , .., m n } be a collection of slopes in RP. There is a finite subgroup, L P F ⊂ PGL 2 R, that fixes P F set-wise.
Lift L P F to GL 2 (R) by taking L F = L P F Z(GL 2 R) ∩ {A ∈ GL 2 R | det(A) = ±1}. We call L P F the group of symmetries of F , and call F symmetric if L F acts by isometries.
Proposition 3.10. For any collection F of n ≥ 3 distinct lines through the origin, there is a symmetric representative of the linear equivalence class of F . Choosing an isometry class of symmetric representative is equivalent to choosing a Euclidean metric on R 2 for which F is symmetric.
Proof. L F is finite. Define a new metric on the plane by The group L F acts isometrically on the plane with this metric. There is an A F ∈ GL 2 R such that x, y L F = A F x, A F y , so A F F is a symmetric representative of the linear equivalence class of F .
Conversely, suppose F is a symmetric representative for the linear equivalence class of F . Suppose A 1 and A 2 are matrices such that | det(A i )| = 1 and A i F = F . Then A 1 A −1 2 ∈ L F . Since F is symmetric, this means the A i differ by an isometry, so For n = 2 we will consider two orthogonal lines to be a symmetric pattern, but the group of symmetries in this case is not a finite group.
For n = 3 there is a single linear equivalence class. There is, up to isometry, a unique symmetric representative, consisting of three lines meeting at angles π 3 . The group of symmetries is isomorphic to S 3 .
For n = 4 there are infinitely many linear equivalence classes, indexed by the cross ratios [−1, 0). Each has, up to isometry, a unique symmetric representative, and a transitive group of symmetries. When the cross ratio is −1 the group of symmetries is isomorphic to the dihedral group of order 8. Otherwise, the group of symmetries is isomorphic to Z/2Z × Z/2Z.
For n = 5 there is no longer a unique symmetric representative for every linear equivalence class. Indeed, there are five-line patterns with trivial group of symmetries. In such a class, every member is symmetric, so the pattern does not determine a canonical choice of metric on the plane.

Coarse Bass-Serre Complex
It is possible to relax some of the group theoretic restrictions from Section 2.2 and still get a geometric model quasi-isometric to G = π 1 Γ. Following the proof of Lemma 2.9 of [9], we construct a coarse Bass-Serre complex X → DΓ to serve as a geometric model for G.
Let Γ be a graph of groups for a tubular group G = π 1 Γ.
Let v be a depth zero vertex of Γ, and e an edge of Γ incident to v at endpoint η.
Suppose A is a group quasi-isometric to Z n . The group A has a finite index normal subgroup B ∼ = Z n [4]. There is a quasi-isometry, f B : A → B, at bounded distance from Id A , with f B | B = Id B . Furthermore, f B takes cyclic subgroups of A to within bounded distance of cyclic subgroups of B.
Applying this reasoning to G v and G e , The usual inclusion of Z 2 into R 2 is a quasi-isometry, and the subgroup x a y b includes into the line through the origin with rational slope b a . In this way, each edge incident to v is associated to a line in R 2 . Let F v be the set of distinct lines. The affine pattern induced by this set is called the edge pattern, and is well defined up to linear equivalence. If F v contains n distinct lines, we will say that v has n lines or is an n-line vertex. Furthermore, we can choose a new Euclidean metric on R 2 to make this pattern symmetric.
Let X q → DΓ be a Bass-Serre tree of spaces for Γ. For each γ ∈ VEDΓ , let h γ : X γ → X γ , where X γ is either R or R 2 and h γ is the quasi-isometry given by restricting to a finite index normal abelian subgroup and then including into X γ .
For each vertex v ∈ VDΓ , and each incident edge e ∈ EDΓ , let F ev : X e → X v be the attaching map. Define a new attaching map by and gluing according to the new attaching maps. The h γ have uniform quasi-isometry constants, since the underlying graph was finite, so they piece together to give a quasi-isometry h : X → X . Since G was quasi-isometric to X, we now have that G is quasi-isometric to X . The action of G on X is quasi-conjugated by h to give a proper, cobounded quasi-action of G on X . The space X is still a tree of spaces over DΓ , and X → DΓ is called a coarse Bass-Serre complex.
When v is a depth zero vertex, the edge spaces of the incident edges attach to X v along lines of the edge pattern in X v .

Contraction Factors and Height Change
Let e be an edge of DΓ , and let v i be the vertex at endpoint (e, i) of e, for i = 0, 1. For each i, F evi maps X e = R within bounded distance of a line in X vi , and there is a factor l i such that d X v i (F evi (x), F evi (y)) = l i d X e (x, y) to within bounded additive error. Define the contraction factor across e to be l1 l0 and the height change across e to be: Metrize the strip X e × [0, 1] as the strip 0 ≤ y ≤ 1 in the plane with metric ( l1 l0 ) 2y dx 2 + dy 2 , so the edge strips are horostrips in a plane of constant curvature −(ln 11 l0 ) 2 . Without changing the quasi-isometry type, we can change X by a bounded amount so that F evi glues X e × {i} isometrically along a line in X vi .
Let p be vertical projection from the bottom (i = 0) of the strip to the top (i = 1) of the strip. The map p is closest point projection. If a and b are points in the bottom edge of the strip, and d i is the distance in X e × {i}, then: For vertices v, w ∈ DΓ , the height change from v to w, h(v, w), is the sum of the height changes across the edges of the geodesic between v and w. This quantity will sometimes be called the height of w relative to v.
Remark. If an edge has height change h that means that closest point projection across the edge scales distances by the same amount as closest point projection between two horizontal horocycles whose y-coordinates (heights) differ by h in the plane with metric ( 1 2 ) 2y dx 2 + dy 2 . The obvious choice would have been to define height change using the natural logarithm, in which case the analogy would be to the hyperbolic plane. The choice of log 2 turns out to be the convenient choice when relating height change to isoperimetric function, but the theory is the same regardless of which base is chosen.
Example 3.11. Suppose we have an edge e going from vertex v to vertex w. Suppose we have chosen metrics on X v and X w so that the stabilizer subgroups are the usual integer lattice in the plane, and the edge injections for e take the generator of G e to a generator in G w and a product of the generators of G v , see Notice that we get a non-zero height change even though we have identified primitive elements.

Geometric Models for Two Tubular Groups
The coarse Bass-Serre complex, X , will serve as the geometric model for its tubular group. We will have no further use for the original Bass-Serre complex.
From this point forward, given two tubular groups, G i = π 1 (Γ i ), for i = 1, 2, X will always refer to the geometric model for G 1 , and Y will always refer to the geometric model for G 2 .

Examples of Tubular Groups
We will spend some time discussing a particular family of tubular groups that can be realized as the fundamental group of a graph of groups with one Z 2 vertex group and edge injections contained in three distinct cyclic subgroups. This family is of particular interest for a few reasons: • The groups have small enough presentation that they are practical to work with. In Example 5.5 we will give a complete quasi-isometry invariant for members of this family.
• There is only one affine equivalence class of 3-line pattern, so the fact that equivalence classes of edge patterns are quasi-isometry invariants, Corollary 3.9, provides no information.
• 3-line patterns are rigid, so we will have to worry about preserving height change. This results in a surprisingly delicate quasi-isometry classification.
• Wise's group and the Brady-Bridson groups all belong to this family. Recall that the Brady-Bridson groups have isoperimetric exponents that form a dense subset of [2, ∞), so we know already that there must be countably many different quasi-isometry classes within the family. Let Γ be the graph of groups in Figure 2. The small arc joining edges e and f near their initial endpoints is a visual cue to indicate that the corresponding edge injections map into coarsely equivalent subgroups.
Let F be the set of lines through the origin of distinct slopes 0, s r , and u t . Let A . Pull back the metric on R 2 according to the matrix A, as in Proposition 3.10. This makes the three-line pattern generated by F symmetric. The height change across e is: The height change across f is: A special case is a Brady-Bridson group BB(p, r) where 0 < p = q < r = t, s = 1, and u = −1. For such a group the height changes across the two edges are: The possible values of λ are dense in (−∞, −1). Brady and Bridson have shown [2] that the group BB(p, r) has Dehn function: This proved that there are no gaps in the isoperimetric spectrum beyond 2.
Proposition 3.12. Suppose we are given height changes λ and µ and four indices of edge inclusions, p, q, m = gcd(r, s), and n = gcd(t, u). These can be realized in a tubular group as in Figure 2 if and only if 2 λ and 2 µ are rational and, as reduced rationals, q 2 µ n = i j and p 2 λ m = i k where i, j, and k are pairwise coprime.
Proof. If these constants did arise from a tubular group, the matrix A that was used to define the metric on the torus allows us to realize the group G v as a lattice in R 2 . In this lattice (1, 0), p 2 λ m (1/2, √ 3/2), and q 2 µ n (−1/2, √ 3/2) must be primitive elements, since these are the images of generators of maximal cyclic subgroups in G. These three elements generate a lattice in which each of them is primitive only if p 2 λ m and q 2 µ n are rational and, as reduced rationals, have the same numerators and relatively prime denominators.
For the converse, choose any g ∈ Z such that Choose any h coprime to g, 1+gj k , and i. Let r = mi 1+gj k , s = mhj, t = ngi, and u = nhk. With these choices, the graph of groups in Figure 2 gives the desired group.
Corollary 3.13. For any numbers λ and µ such that 2 λ and 2 µ are rational, it is possible to construct a tubular group as in Figure 2 where the height changes across the two edges are λ and µ.

P-sets
No two depth zero vertex spaces are bounded Hausdorff distance from one another. However, there is a weaker characterization of closeness of two local spaces according to whether they are close on unbounded subsets. We define the corresponding relation on the vertices and edges of the Bass-Serre tree: Definition 3.14. Two elements x, y ∈ VEDΓ satisfy Relation P if X x c ∩ X y is unbounded.
Quasi-isometries respect vertex and edge spaces, and preserve boundedness and unboundedness, so Relation P is invariant under quasi-isometry. Definition 3.15. A P-set of DΓ is a maximal subset of VEDΓ such that any two elements satisfy Relation P. Proposition 3.16 (Properties of P-sets).

A P-set is a subtree of DΓ .
2. Every depth zero vertex of a P-set is adjacent to infinitely many other vertices in that P-set.
3. An n-line, depth zero vertex belongs to n distinct P-sets.
4. Edges and positive depth vertices belong to exactly one P-set.
5. Any two P-sets are either disjoint or intersect in exactly one vertex, which is necessarily a depth zero vertex.
Proof. Let e 1 and e 2 be edges in DΓ incident to a common depth zero vertex, v. The vertex v satisfies Relation P with either of the e i .
The edges e 1 and e 2 satisfy Relation P if and only if their edge strips glue to X v along parallel lines.
The list of properties follows easily from this observation The fundamental group G = π 1 (Γ) quasi-acts on X. Quasi-isometries preserve Relation P, so the action of G on DΓ induces an action of G on the set of P-sets of DΓ .
Definition 3.17. Within a P-set S, two depth zero vertices v and w are of the same type if ∃g ∈ Stab G (S) such that gv = w.
Type is an equivalence relation among depth zero vertices of a fixed P-set. For an n-line depth zero vertex, the equivalence class of the vertex under the action of the whole group splits into at most n vertex types in S.
If there is a height change between vertices of the same type in a P-set, the geodesic segment joining them projects to a non-trivial loop in the underlying graph of Γ. The group element corresponding to this loop is an infinite order element of the P-set stabilizer. Iterating the action of this group element gives vertices of the P-set all of the same type occurring at an unbounded set of heights.
If there is zero height change between every pair of vertices of the same type in a P-set then, since there are only finitely many vertex types, the vertices of the P-set occur at only finitely many heights. Thus, there is bounded height change between any two vertices of the P-set.
For each orbit of P-sets, pick a representative S i and fix an ordered list of representative x i,j for the vertex types in S i . Suppose S and R are P-sets, x and y are vertices in R, g ∈ G such that gR = S, and k ∈ Stab G (R) such that kx = y. Then gkg −1 ∈ Stab G S and gkg −1 gx = gkx = gy, so the action of the group takes vertices of the same type in one P-set to vertices of the same type in another. Thus, we can fix an ordering of vertex types for each equivalence class of P-set.
We will say that x ∈ V 0 S is of type {[S i ], j} with respect to S if there is some g ∈ G such that gS = S i and gx = x i,j . Proposition 3.18. Suppose v ∈ V 0 DΓ , and R and S are P-sets containing v. There is an element g ∈ Stab G (v) such that gR = S if and only if v is of the same type with respect to both R and S.
Proof. Suppose ∃g ∈ Stab G (v) such that gR = S. The P-sets R and S then belong to the same equivalence class; call it Definition 3.19. The tree of P-sets, T Γ , of a tubular group, G = π 1 (Γ), is given by: • Edges are determined by inclusion of vertices in P-sets. Each edge is assigned length 1 2 . The collection of P-sets is a cover of DΓ by subtrees that intersect pairwise in at most a single vertex. The nerve of such a cover is simply connected, and T Γ is a deformation retraction of this nerve. So, T Γ is, in fact, a tree.
It will be convenient to extend the notion of height change across an edge to some of the edges of T Γ . If R is a P-set with bounded height change, pick some adjacent depth zero vertex, v, of maximal height. For any vertex w adjacent to The action of G on DΓ induces an action of G on T Γ .

Quasi-isometries Between Tubular Groups
In Section 4.1 we look at properties of the map of trees of P-sets induced by a quasi-isometry of tubular groups. A map that satisfies the same properties we call "allowable." In Section 4.2 we show that an allowable isomorphism of trees of Psets exists if and only if there is a "consistent set of strategies," and we show that we can decide in finite time whether such a set of strategies exists. In Section 4.3 we take a consistent set of strategies and use it to build a quasi-isometry of tubular groups. Thus, we conclude that the existence of an allowable isomorphism of trees of P-sets is not only a necessary, but also sufficient condition for the existence of a quasi-isometry between tubular groups, and the success or failure of the algorithm for finding a consistent set of strategies determines the existence or non-existence of a quasi-isometry between the tubular groups.

Allowable Isomorphisms of Trees of P-Sets
Suppose G 1 = π 1 (Γ 1 ) and G 2 = π 1 (Γ 2 ) are tubular groups, with trees of P-sets T 1 and T 2 , respectively. A quasi-isometry, ψ : Recall that the P-sets R 1 , . . . , R n adjacent to a depth zero vertex v are in oneto-one correspondence with the families of parallel lines forming the edge pattern in the vertex space of v. To satisfy edge pattern rigidity, the bijection must correspond to an affine equivalence between the edge patterns of X v and Y ψ # (v) .
If this restriction is satisfied for every depth zero vertex, then ψ # will be called locally allowable.
Define a rigid component of T i to be a connected component of An induced isomorphism ψ # must take 2-line, depth zero vertices to 2-line, depth zero vertices, so ψ # takes rigid components to rigid components. Lemma 4.1. A quasi-isometry between tubular groups induces an isomorphism between their trees of P-sets that is coarsely height preserving on rigid components.
Proof. Within a P-set Space: A P-set space is metrically a warped product of a tree with R, with height as the warping function. This also the case for Baumslag-Solitar groups, and the proof that a quasi-isometry is coarsely height preserving within a P-set space is similar to the proof that a quasi-isometry of Baumslag-Solitar groups is coarsely height preserving [14,Lemma 4.1].
Let R be a P-set in a tubular group Suppose v 0 and v 1 are two vertices in R. In the geodesic of DΓ joining v 0 and v 1 , let e i be the edge incident to v i . Let L v,e be the line in X v to which the edge strip for an incident edge e attaches. Let x and x be an arbitrary pair of reference points in L v0,e0 .
Suppose we have a quasi-isometry, φ, of tubular groups that restricts to a (K, C)-quasi-isometry of the X vi . Let φ # be the induced bijection of depth zero vertices. Let S = φ # (R) and let w i = φ # (v i ). Let f i be the edge incident to w i on the tree geodesic joining the w i . A quasi-isometry coarsely preserves closest point projection. That is, the following diagram commutes up to error E which depends on global constants and on d DΓ (v 0 , v 1 ), but not on the v i or the particular points in L v0,e0 .
We know that φ(x) and φ(x ) map to within some uniform distance, D, of a line The situation is summarized in Figure 3.
For any δ > 0 we can take x and x far enough apart so that The reverse inequality follow from a similar computation, so that height between vertices in a P-set is preserved by quasi-isometries of tubular groups, up to an additive error depending on the quasi-isometry constant.
From One P-set Space to Another : Let v 0 , v 1 , and v 2 be depth zero vertices such that v i and v i+1 belong to a common P-set, but v 0 and v 2 do not. Assume v 1 is a vertex with at least three lines. For i = 0, 1, let e i be the edge adjacent to v i in the tree geodesic joining the v i . For j = 1, 2, let e j be the edge adjacent to v i in the tree geodesic joining the v i . Pick reference points x and x ∈ L v0,e0 as in the previous case. Projecting these points to X v2 would not give us much information because X v0 c ∩ X v2 is a point in X v1 . We can not do two separate height change calculations within P-sets because we need the height error bound to be independent of the number of P-sets traversed. Instead we link these calculations together by exploiting the fact that the restriction of a quasi-isometry to a vertex space with at least three lines expands by the same factor in all directions.
Pick reference points z and z ∈ L v1,e 1 such that Since φ| Xv 1 stretches by the same amount in every direction, we have Thus, for any δ 1 > 0 we can take x and x far enough apart so that Now we can chain together the height change calculations from the different P-sets and get cancellation at the intermediate vertices. We find that for any δ 2 > 0, if x and x are sufficiently far apart then So as before we find that A similar computation produces the reverse inequality.    , k l } with respect to R a,i,l . This is the set of types that x a,i takes with respect to the P-sets containing it.

Finding Allowable Isomorphisms
Similarly, consider the set A linear equivalence between the edge patterns in X xa,i and Y y b,j gives a bijection between P-sets adjacent to x a,i and y b,j , which in turn gives a bijection of these sets of types. We will let e ij be any bijection of these sets that can be induced by a linear equivalence of edge patterns and that includes Remark. If we knew that for any parallel family of edge lines in a vertex space, the subgroup of the vertex stabilizer that fixes that family also fixes each of the other families, then the set of types that that depth zero vertex takes has no duplicate entries. This would be true, for instance, if the tubular group were torsion free. Specifying a type picks out a parallel family of lines in the vertex space, and we could put an equivariant numbering on these families. Then, instead of a bijection of sets of types as we defined above, we could just associate to a linear equivalence of edge patterns a permutation describing which families go to which families. This may fail for groups with torsion, but Proposition 3.18 shows that it is just the ordering of the sets that is ambiguous. In either case, there are at most two distinct bijections to consider. An extension provides instructions for extending a tree isomorphism in a locally allowable way. Suppose R ∈ T 1 and S ∈ T 2 are P-sets and we have constructed a map sending R to S. To extend the map, choose any bijection V 0 R → V 0 S such that vertices of type {[R], i} map to vertices of type {[S], j} if and only if e ij = 0. The value of e ij then tells how to extend to the next level of Psets. For the purposes of tree isomorphisms, the particular bijection V 0 R → V 0 S does not matter, but more care will be required when building quasi-isometries in Section 4.3.
Conversely, given an allowable isomorphism φ :  The label of a terminal vertex is the match associated to it. A strategy can be simplified by considering at most three terminal vertices for each label: one with maximum height error, one with minimum height error, and one with undefined height error. Thus, we can assume that the number of terminal vertices of any strategy is at most 3mn.

Strategies
A strategy records how the boundary of a neighborhood of a P-set R in T 1 maps to the boundary of a neighborhood of S in T 2 when mapped according to an extension E for ([R], [S]).
If S is a strategy, define

TERM(S) = {terminal vertices of S}
A set of strategies will consist of a graph, each of whose vertices is labeled by a match and two (not necessarily distinct) strategies for the match, one called the positive strategy and the other called the negative strategy. There will be at most one vertex labeled by a given match, so at most mn vertices.
For each strategy in the set, add an edge to the graph from the root vertex of the strategy to each terminal vertex of the strategy. Label the edge by the sign of the strategy and the height error, if defined, for the appropriate terminal vertex.

Consistency
We need to check that building according to the set of strategies will not create unbounded height error. It is necessary that each match consists of two P-sets of bounded height change or two P-sets of unbounded height change, but we also must control accumulation of height error created by the strategies.
For P-sets of bounded height error, the type of a vertex determines its relative height. Choosing an extension therefore determines height errors in a neighborhood of the P-set.
We do not need to worry about height change when it comes to P-sets of unbounded height change. We will see in Lemma 4.9 that the presence of depth zero vertices at an unbounded set of heights allows us to correct any height error.
Let M 1 , . . . be a list of the matches of P-sets of bounded height change that label vertices of G. For each i, add to the set of inequalities: Suppose v ∈ TERM(S − i ) has a defined height error, and the label of v is M j . Let E be the height error of v in S − I . Add the following inequalities to the set: If the system of inequalities has a solution then height error is well controlled. The L i and U i provide bounds.
If such a system of inequalities has a solution, then it has a solution such that all the U i are positive, all the L i are negative, and all the M i are zero. Furthermore, given any fixed B, there is a solution such that, for all i, U i > B and L i < −B.
Note that if a positive strategy for a match M i adds an edge with negative height error that leads back to M i , then the set of strategies can not be consistent.
Similarly, a negative strategy should not create a length one loop with a positive height error.
The next lemma shows that from an allowable isomorphism we can derive a consistent set of strategies. The idea of the proof is to consider the places where the isomorphism has the worst height errors and choose strategies according to what happens in neighborhoods of those bad places.  ). If U i is not achieved, let S − i be any strategy that occurs for R with height error arbitrarily close to U i . These will be the negative strategies.
Pick positive strategies S + i analogously, using the L i . The set of strategies chosen in this way is consistent, although the height error bounds may be larger than for φ.

Theorem 4.5.
There is an algorithm that in finite time either produces a consistent set of strategies for two trees of P-sets or decides that no such set exists. Furthermore, the algorithm is guaranteed to succeed if the trees of P-sets came from quasi-isometric tubular groups.
Proof. A set of strategies is completely determined by the matches in it and the choices of extensions for those matches. If T 1 and T 2 are as above, then there are at most mn matches and each extension has at most max{ρ(a)} × max{σ(b)} entries. Each entry takes one of at most 3 values, so we have at most 3 2mn×max{ρ(a)}×max{σ(b)} possible candidate sets of strategies.
Enumerate this list of candidates and check if there is a candidate that is actually a consistent set of strategies.
In light of Corollary 4.3 and Lemma 4.4, success is guaranteed if the trees came from quasi-isometric groups.

Building Quasi-isometries
In this subsection we show how to build a quasi-isometry of tubular groups from a consistent set of strategies. In Section 4.3.1 we prove some auxiliary lemmas about quasi-isometries of trees. In Section 4.3.2 we build quasi-isometries of Pset spaces. In Section 4.3.3 we assemble quasi-isometries of P-set spaces to get a quasi-isometry of tubular groups.

Some Lemmas on Trees
We leave the world of tubular groups for a moment to prove some lemmas about quasi-isometries of trees that we will need to build quasi-isometries of P-set spaces.
Let FIN(V ) denote the set of all finite subsets of V .
Theorem (Hall's Selection Theorem). Let ω : V → FIN(W ). There exists φ : A tree will always mean a simplicial tree with edges of length 1. A line r in a tree V means an isometric embedding r : R → V that takes integers to vertices.
A tree is δ-bushy if every vertex is within distance δ of a vertex whose complement has at least three unbounded components.
A line r has C-coarse slope m if, for all a, b ∈ R, |h(r(a), r(b)) − m|b − a|| ≤ C Let E r (a, b) denote the number of edges incident to the segment of r from r(a) to r(b). A line has C-coarse edge density ρ if, for all a, b ∈ R, |E r (a, b) − ρ|b − a|| ≤ C A lamination of V is a family of lines such that every vertex belongs to exactly one of the lines.
Whyte proved [14] the quasi-isometry classification of graphs of Z's by matching laminations of their Bass-Serre trees. In Lemma 4.6 we will give a generalization of Whyte's argument, but first we will give an outline of his proof. The goal is to build a coarsely height preserving quasi-isometry between two trees, V 1 and V 2 .

Sketch.
Step 1: Reduce to the case of homogeneous trees.
Step 2: For any sufficiently small β there is a lamination of V i by lines of coarse slope β. Since the V i are homogeneous, any line in the tree has coarse edge density ρ i equal to the valence minus two. Choose sufficiently small β i so that: Choose laminations of the V i by lines of slope β i .
Step 3: The quasi-isometry will be built line-by-line. Given a line r i from each lamination, there is an obvious coarsely height preserving quasi-isometry: rescale the line from V 1 by a factor of β1 β2 .
Step 4: Since the ratio of the slopes was equal to the ratio of the edge densities, a segment of r 1 has approximately the same number of incident edges as its image in r 2 . This allows us to produce a height respecting matching of lines of the lamination of V 1 adjacent to r 1 to lines of the lamination of V 2 adjacent to r 2 .
We wish to generalize this argument to trees that are not Bass-Serre trees of a group. Let Γ be a finite, connected graph with directed edges. The graph Γ may have edges with the same initial and terminal vertex, and may have multiple edges between a pair of vertices. Associate a height change to each edge. Suppose there is a loop in Γ such that the sum of the height changes across edges of the loop is strictly positive.
Consider a bounded valence tree with directed edges covering Γ, V p → Γ, such that for every vertex v ∈ V , the edges coming in to v cover the edges coming in to p(v) at least two to one, and similarly for the outgoing edges. If Γ is not just a single vertex with a single edge, then this condition can be relaxed slightly. If there is an edge e and a vertex v in Γ such that v is the initial and terminal vertex for e, then at a vertex in p −1 (v) there need be only one incoming and one outgoing edge covering e.
The height change of an edge in V is the height change of its image in Γ.
To prove there is a coarsely height preserving quasi-isometry between two such trees we follow Whyte's outline. We can not reduce to homogeneous trees, so there is no reason to believe that we can choose a lamination whose lines have a well defined edge density. However, choosing lines with well defined slopes and edge densities really amounts to saying that there are uniform proportionality constants such that for any segment of a line of the lamination, the length of the segment is proportional to the height change along the segment and to the number of edges incident to the segment. We do not need this much to make Whyte's argument work. Really we need two conditions. We need bounds on the ratio of height change to length of a segment so that we can build height preserving quasi-isometries along the lines, and we need the ratio of height change to number of incident edges to be uniform on all segments of lines of the lamination so that we can match adjacent lines.
Lemma 4.6. Let V p → Γ and W q → Γ be two trees as described above. There is a coarsely height preserving quasi-isometry between V and W . Furthermore, the quasi-isometry and coarseness constants can be bounded in terms of information from Γ and Γ and the valence bounds for V and W .
Proof. Assume W is the (2, 2)-homogeneous tree, that is, the tree that has at every vertex two edges that increase height by one, and two edges that decrease height by one. For the general statement of the Lemma it suffices to compose two instances of this special case.
Let M be the maximum height change across an edge of Γ. Let δ be the diameter of Γ. Let N be the number of vertices of Γ. Let L be the maximum valence of a vertex in V .
Step 1: Take a maximal subtree of Γ with a basepoint and a family of lifts of this subtree to V such that every vertex of V belongs to exactly one lift in the family. The covering is locally 2 to 1 on edges of the maximal subtree, so such a family exists. Collapsing these subtrees is a (δ + 1, δ)-quasi-isometry to a tree, V . We can make it 2δM -coarsely height preserving by declaring the height change between two vertices of V to be the height change between lifts of the basepoint in the two preimages in V . The maximum height change across an edge of V is at most M = (2δ + 1)M . By assumption, there was a loop in Γ that strictly increased height, so every vertex of the tree has at least one edge that increases height and one that decreases height. Furthermore, there is no vertex that has exactly one edge that decreases height and all the rest increase height, or vice, versa. A vertex with only one edge that decreases height or only one edge that increases height must also have edges with zero height change. If any such vertices exist, then further collapse a collection of disjoint, zero-height-change edges so that every vertex in the tree has at least two incident edges that increase height and at least two that decrease height.

Vertices of V have valence between 4 and 2N L.
Step 2: Let ρ = 2N L − 2 ≥ 2. Let 0 < α ≤ 1 be some number such that every vertex of V has at least two edges that increase height by at least α and two edges that decrease height by at least α. Such an α exists since there were only finitely many possible height changes across an edge of V .
There is a lamination of W by lines of 2-coarse slope β. Such a lamination can be built inductively. Start at some vertex and choose an incident edge to start a line. To continue a line choose either an edge that increases height or decreases height as appropriate to keep the slope of the line as close as possible to β. An appropriate edge is always available since at every vertex there are two edges that increase height and two edges that decrease height.
Repeat this process for every vertex adjacent to the lines that have already been built, etc.
Claim. There exists a constant J > 0 and a lamination of V by lines r such that, for all m, n ∈ R, Step 3: Assuming the claim, we build a quasi-isometry line-by-line using the laminations of V and W .
For a line r in the lamination of V , It is sufficient to define a quasi-isometry on the integer points.
Assume that φ(r(0)) = r (0). Let these points be the basepoints of their respective trees, and define height in each tree relative to the basepoint, that is, h(r(a)) = h(r(0), r(a)).
For z ∈ Z pick a z ∈ Z so that |h(r (z )) − h(r(z))| ≤ 1 2 and define φ(r(z)) = r (z ). Such a z exists because r has nonzero slope and height changes by ±1 across each edge of W .
For any z 1 , z 2 ∈ Z, Combining these inequalities with the bounds on height change in terms of segment length for r and the fact that r has 2-coarse slope β, we find: Thus, φ is a coarsely height preserving quasi-isometry.
Step 4: For x < y ∈ R, let V 1 (r)[x, y] be the set of vertices adjacent to r with height between x and y.
We need a K > 0 so that for all x and y, and vice versa.
Then Hall's Selection Theorem gives injections between vertices adjacent to r and vertices adjacent to r that are K-coarsely height preserving, and the Schroeder-Bernstein Theorem applied to these injections gives a bijection.
Suppose a < b are such that h(r(a)) = x and h(r(b)) = y. Then: Points on r distance at least c apart differ in height by more than M , so if z < a − c then x − h(r(z)) = h(r(a)) − h(r(z)) > M . Since edges of V change height by at most M , every vertex adjacent to r(z) has height strictly less than x, so no vertices adjacent to r(z) belong to V 1 (r)[x, y].
By similar arguments, no vertices adjacent to r(z) for z > b + c are in V 1 (r)[x, y], and all vertices adjacent to r(z) for z ∈ [a + c, b − c] are in V 1 (r)[x, y]. Therefore: We can estimate these quantities: This gives us: A similar computation for r shows: Let A = max{ 4 β α(3c + 2) + 7 2 J , 20 β }, and let K = Aβ 2 . Then Step 5: Induct.
Proof of the Claim It is sufficient to take J = 2J where J = M + α. Let r(0) be some vertex. There is an edge incident to r(0) that increases height by at least α. Follow this edge to r(1).
Continue by induction. Suppose that r has been extended to r(n). If then follow an edge that decreases height by at least α to get to r(n + 1). There are at least two edges incident to r(n) that decrease height by at least α, so it is possible to extend without backtracking.
Without backtracking, follow an edge that increases height by at least α to get to r(n + 1).
Repeat this process to build a ray from r(0) such that The union of the two rays gives the desired line. Take some vertex adjacent to this line. This vertex has at least two edges that increase slope, and two edges that increase slope. Only one of these edges is the one that connects the vertex to the line, so we can repeat the construction to get another line through this vertex disjoint from the first line. We can continue to extend in this way to get a lamination of V .
It will be important that the quasi-isometries we build are bijections on the vertex sets of the trees. Since the trees we are working with are non-amenable this can always be arranged. The n = 1 case of the following lemma is a special case of Theorem 4.1 of [13].
Lemma 4.7. Let V and W be δ-bushy trees, both with variable valence at most b. Suppose ψ : V → W is a quasi-isometry. Given finitely many disjoint, δcoarsely dense subsets V 1 , . . . , V n ⊂ VV and W 1 , . . . , W n ⊂ VW , there exists χ : ∪V i → ∪W i a bilipschitz bijection that respects the partitions, χ(V i ) ⊂ W i for all i. The map χ extends to a quasi-isometry V → W . Furthermore, χ is bounded distance from ψ, and the quasi-isometry constants depend only on b, δ, and the quasi-isometry constants of ψ.
Proof. The trees V and W are both quasi-isometric to the Cayley graph of the free group of rank 2, so they are both non-amenable. Suppose ψ is a (λ, )-quasiisometry.
Since each of the V i and W i are δ-coarsely dense, ψ can be changed by distance at most δ so that for each i we have a (λ, 2δ(λ+ ))-quasi-isometry ψ i = ψ| Vi : V i → W i . The V i and W i are also non-amenable, since they are coarsely dense subsets of non-amenable sets.
For each ψ i apply Theorem 4.1 of [13] to get a bilipschitz bijection χ i : V i → W i . The V i are disjoint, so we can assemble the χ i to get a bilipschitz bijection χ : ∪ V i → ∪W i that respects the partitions. Finally, since ∪V i is coarsely dense in V , χ can be extended to a give a quasi-isometry V → W .

The Pieces
A P-set space is the preimage in the model space of a P-set in the Bass-Serre tree. In Lemma 4.8 and Lemma 4.9 we construct quasi-isometries of P-set spaces. In Theorem 4.10 these are pieced together to give a quasi-isometry of tubular groups.
There are two complications to consider when building quasi-isometries between P-set spaces. First, depth zero vertex spaces belong to several different P-set spaces. We must take care to build quasi-isometries of P-set spaces that can later be pieced together into a quasi-isometry of tubular groups. Second, to make use of Theorem 4.5 we need to build according to a given extension, which puts type restrictions on which vertex spaces map to each other.
Let R be a P-set in DΓ . Let v 0 be some depth zero vertex of R. Height for other points of R can then be defined relative to v 0 .
Put standard Euclidean coordinates on X v0 in such a way that the edges of R glue onto X v0 along lines of the form t × R.
The second coordinate can be projected over all of X R , giving coordinates on X R of the form tree × R, with the R factor scaled according 2 −height . With these coordinates, an edge space or a positive depth vertex space is just (t, R), for some t, and the length of (t, If v is a depth zero vertex of R, parameterize the direction orthogonal to the lines of edge attachments so that the edge leading back to v 0 is at coordinate 0 and so that d Xv Define a map B : R → tree by lifting to X R and projecting to zero in the second coordinate. In B(R) the depth zero vertices are "blown up" into lines. Edges of B(R) contained in a depth zero vertex space will be called horizontal. Conversely, edges of B(R) that cross an edge space will be called vertical.
A horizontal component of B(R) is the blow up of some depth zero vertex. A vertical component is a connected component of the complement of the interiors of the horizontal edges.
We will build a quasi-isometry of B(R) that can be extended to a quasiisometry of the P-set spaces. At first glance the situation here is very similar to the situation described in the previous section, we want a height preserving quasi-isometry of trees and we (almost) have a lamination of the trees by the collection of horizontal components. However, there are some important differences, and the techniques of Lemma 4.6 are not enough in this situation. One difference is that the laminations in Lemma 4.6 were not canonical. We chose the laminations for convenience, there was no reason a quasi-isometry had to preserve lines of the lamination, but by making convenient choices we could build a quasi-isometry that did. In B(R) we do not get to choose. The lamination is forced on us because we know the vertex spaces must be preserved.
A second difference is that in Lemma 4.6 the construction of quasi-isometries on the lines of the laminations was engineered so that we could get both height change and relative numbers of incident edges right. We can not hope to be so lucky in B(R). For one thing there are adjacent vertices of different types that may have different edge densities. For another, each horizontal component represents a vertex space that belongs to a number of different P-sets. If we define the quasi-isometry to meet the needs of a particular P-set, we will not be able to glue up all of the different quasi-isometries at the end. Because of these problems we will not be able to match adjacent lines in the laminations as we did in Lemma 4.6. However, it was not really necessary for a quasi-isometry to match adjacent lines of a lamination to adjacent lines of the other; it is good enough to take nearby lines to nearby lines. This is the major difference between Lemma 4.8 and Lemma 4.6, we get around the additional complications present in B(R) essentially by showing that we can find a matching between suitable nearby horizontal components.
A third difference, which is a technical detail, is that in Lemma 4.6, long enough segments in the lines of the lamination always had strictly positive height change. This was convenient because, when matching lines adjacent to a line r to lines adjacent to a line r , we did not have to worry about relative distances between lines adjacent to r compared to the distances between their images adjacent to r . Getting the heights right ensured that the distances would be right too. In B(R) the lines of the lamination are called "horizontal components" exactly because there is no height change along them. This means we have to work a little harder to make sure the relevant distances work out correctly.
The next lemma gives a quasi-isometry of a P-set space for a P-set of bounded height change. The various parameters just say that this is a quasi-isometry, built according to an extension E, starting from a previously defined map on one of the depth zero vertex spaces.

Φ is a bilipschitz bijection
Proof. Pick some J such that J 2 is a bound for the absolute value of the height change between any two vertices of R or any two vertices of S.
For any x ∈ R, let h(x) = h(x 0 , x), and similarly for y ∈ S with respect to y 0 . Let x be a depth zero vertex of R. Let e be an edge of R incident to x. Since Stab G1 (e) has infinite index in Stab G1 (x), the orbit of e by Stab G1 (x) ∩ Stab G1 (R) contains infinitely many other edges incident to x. The edge spaces for these edges glue on to X x along parallel lines, and the distance between such lines can be bounded in terms of [x], [R], and [e].
Pick some L such that for each P ∈ {R, S}, and every v ∈ V 0 P , any open interval of length L in B(v) has at least two incident vertical edges from each Stab G (v) ∩ Stab G (P ) equivalence class of edge incident to v, and at least three total incident vertical edges.
Choose coordinates for X R as discussed above. Choose coordinates for Y S in a similar fashion, with the following provision. If we already have a map X x0 → Y y0 , choose the coordinates of Y y0 so that the origin of Y y0 is the image of the origin of X x0 and so that map preserves the orientation of the second coordinate.
For every v ∈ V 0 P , do the following: Define the basepoint ξ v of B(v) to be the point of B(v) with coordinate zero. Slide any edge incident to the open interval in B(v) to 0. Note that for each v this interval is of length L. These sliding operations change distances between points in different horizontal components, but preserve distance within a fixed horizontal component.
For the vertices of the vertical components that are points of intersection with horizontal components, the type of the vertex is just the type of the vertex in DΓ corresponding to that horizontal component. After sliding, the new vertical components are composed of unions of the original vertical components. In particular, the new vertical components containing ξ x0 and ξ y0 are infinite, bounded valence trees; call them V and W , respectively.
The image of V in Γ 1 is the same as the image of R in Γ 1 . Therefore, the set of vertices of V of any particular vertex type are coarsely dense in V . The diameter of the image of R in Γ 1 provides a coarseness constant.
Similar statements are true for W as well. Let δ be the greater of the diameters of R in Γ 1 and S in Γ 2 .
Every vertex of V and W is distance at most δ from a vertex of valence at least three, and there are no valence one vertices, so V and W are δ-bushy. Also, the valences of V and W are bounded above.
For convenience we will assume that the extension E gives a bijection from vertex types of R to vertex types of S. To arrange this, note that the set of vertices of V of a particular type can be subdivided into a finite number of subsets, each of which is also dense in V , and similarly for W .
Apply Lemma 4.7 to get a quasi-isometry φ : V → W which is a bilipschitz bijection on vertices and respects the partitions into vertex type. The bilipschitz constant, M x , depends only on the valence bounds, bushiness constants, density constants, and number of vertex types. This process will be called extension along a vertical component. Note that every depth zero vertex in V or W is the basepoint of its horizontal component.
Suppose extension along a vertical component identifies ξ x to ξ y . Let For n = 1, 2, . . . , consider the half-open intervals Each of these intervals has length at least L, so there are at least three vertical edges incident to each interval. On the other hand, the lengths of the intervals are bounded above by N = L · 2 J max{ α β , β α }. Extend φ by φ| B(x) : B(x) → B(y) : r → ± β α r. The choice of orientation here is determined by the element e ij associated to x, y. The edge sliding matches up the points to which vertical edges attach, and each of these will be the basepoint of a new vertical component to extend along.
Alternate extending along collections of vertical and horizontal components to build φ.
We make the following observations about this construction: 1. Every vertical edge has at most one endpoint that slides.
2. No edge slides more than once.
3. Sliding an edge only changes distances between points separated by the edge.
4. No edge slides more than distance N .
Therefore, distances in B(V 0 R) and B(V 0 S) change by at most a multiplicative factor of 1 + N . Extension along horizontal components changes distance by at most a multiplicative factor of β α 2 J . Vertical components have valence bounded by N and information from X and Y , so there is a uniform bound M on the bilipschitz constants M x . Thus, β . Geodesics in X R and Y S can be approximated within bounded multiplicative error by paths in which only one coordinate changes at a time, so Φ is bilipschitz on V 0 X R .
The union of vertex spaces is dense in a P-set space, so Φ gives a quasi-isometry of P-set spaces.
We have a similar result for P-sets of unbounded height change.

Φ is a bilipschitz bijection
Proof. The proof differs from the proof of Lemma 4.8 only in the how we extend along vertical components. For i = 1, 2, consider the projection of the appropriate P-set to the graph Γ i . Let µ i be the largest height change that occurs across a single edge in the projection. The edge sliding is set up so that we can apply Lemma 4.6 to find a coarsely height preserving quasi-isometry between the resulting vertical components. Furthermore, the height error can be bounded in terms of the projections to the Γ i . Let K be such a bound; K plays the role in this case that the constant J played in the bounded height change case.
Perform the edge sliding as in the previous Lemma. Suppose V and W are vertical components based at v 0 ∈ B(x) and w 0 ∈ B(y), respectively. Notice that the valence of V at v 0 may depend on β α , since v 0 may not be equal to ξ x . However, every other vertex in V ∩ B(V 0 R) and W ∩ B(V 0 S) is the basepoint of its vertical component, so the valence of the trees at these points is bounded independently of β α . It is possible to "disperse" the extra edges at v 0 by a height and type preserving bilipschitz bijection V ∩ B(V 0 R) to a new tree V . In the same way replace W by a new tree W .
There is some vertex ξ w in W at bounded distance from ξ w0 such that Let φ be a (K + µ 2 )-coarsely height preserving quasi-isometry between V and W that maps v 0 to ξ w . As in the previous Lemma, φ, can then be changed a bounded amount to give a bijection φ of depth zero vertices that respects the partitions by type. Moreover, the amount φ needs to be changed is independent of β α , so the height error is still independent of β α .
The map V → V → W → W is then a bilipschitz bijection: Finally, we adjust this map to ensure v 0 maps to w 0 . The result is the map we will use to extend along vertical components. Note that while the bilipschitz constants depend on β α , the height error at points other than v 0 is bounded independently of β α . Remark. Note the important difference in these two Lemmas. In both cases we start by identifying x 0 to y 0 . The parameters α and β provide an initial height error; think of E = log 2 ( β α ) as the height error at x 0 . In the bounded case, the height error of the other vertices is in [E − J, E + J].
In the unbounded case, E influences the quasi-isometry constants, but the height error of the other vertices is independent of E.

Putting the Pieces Together
The following Theorem shows that a consistent set of strategies can be used to build a quasi-isometry between tubular groups. Lemma 4.8 and Lemma 4.9 provide the basic building blocks, and the quasi-isometry constants are controlled by controlling height error. Two-line, depth zero vertices and P-sets of unbounded height change are flexible enough that height error will not be an issue. In these cases we can choose the quasi-isometry to immediately "correct" any accumulated height error back to some uniformly bounded amount. The danger of compounding height error comes from P-sets of bounded height change connected by depth zero vertices with at least three lines. These height errors are controlled by the set of strategies.
Theorem 4.10. For i = 1, 2, let G i = π 1 (Γ i ) be a tubular group and T i its tree of P-sets. If there is a consistent set of strategies for T 1 and T 2 , then G 1 and G 2 are quasi-isometric.
Proof. Let G be a consistent set of strategies for T 1 and T 2 . We build a quasiisometry Φ : X → Y and an allowable tree isomorphism φ : Let M i be the matches of P-sets of bounded height change occurring in G, and let {U i } and {L i } be height error bounds from the consistency check.
Choose a uniform K such that, for any P-sets R ∈ T 1 and S ∈ T 2 of unbounded height change, there is a quasi-isometry Φ ∞ : X R → Y S as in Lemma 4.9 with height error bounded by K .
In DΓ 1 and DΓ 2 there are finitely many equivalence classes of P-sets of bounded height change, so there is some maximum height change, K , that can occur between depth zero vertices in such a P-set. This implies that for any P-set R ∈ T 1 of bounded height change, any depth zero vertices v, v ∈ R and any isomorphism φ : Let K = max{K , K }. Assume the U i are greater than 2K and the L i are less than −2K.
We build a quasi-isometry inductively P-set space by P-set space. There are a number of cases to consider, but for all cases the outline of the construction is the same. In the cases that follow, we will refer to this process as "extending the maps".
At each step we are given P-sets R, R ∈ T 1 , and a depth zero vertex v ∈ R∩R . We assume that we have a partial tree isomorphism φ : T 1 → T 2 that is defined at least on R, R and v, and a quasi-isometry Φ R : X R → Y φ(R) . We want to extend φ to a neighborhood of R and define a quasi-isometry Φ R : Define a quasi-isometry Φ R : X R → Y φ(R ) by consulting G for an "appropriate" strategy, S, for the match ([R ], [φ(R )]). If R is of unbounded height change there is only one strategy to choose. If R is of bounded height change then we choose the positive strategy if Err φ (R ) < 0 and the negative strategy if Err φ (R ) ≥ 0. Associated to S is an extension E.
from Lemma 4.9 if R is of unbounded height change. The constants α and β are to be determined in the induction steps.
Extend φ from R according to E, using the bijection of depth zero vertices furnished by (Φ R ) # .
In each case below we check that if we started with a P-set R such that Base Case : Pick any P-set vertices R ∈ T 1 and S ∈ T 2 such that ([R], [S]) is the match of a vertex of G. Set φ(R) = S.
Pick any depth zero vertex v ∈ R. Declare v to be the basepoint, so v has height zero and all other heights are determined relative to v.
Consult G for an appropriate strategy S for ([R], [S]) with extension E. If v is of type {[R], i} with respect to R, find some j such that the i, j entry of E is nonzero and choose a depth zero vertex w ∈ S of type {[S], j}. Define φ(v) = w.
Declare w to be height zero, and define heights in S relative to w. Now we have a P-set R, a preferred vertex v ∈ R and a partial tree isomorphism defined at least for v and R, with Err φ (v) = 0. Extend the maps with α = β = 1.
If R is of unbounded height change then by construction the height errors for all the depth zero vertices of R will be in the interval [−K, K]. If R is of bounded height change then for any depth zero vertex v ∈ R, Now there are a number of situations to consider, depending on whether R and R are of bounded or unbounded height change, and whether v has two lines or more than two lines. v has 2 lines: Define height in R relative to v and define height in φ(R ) relative to φ(v).
The height errors of depth zero vertices of R are in [−2K, 2K]. Furthermore, if R is of bounded height change then Err φ (R ) ∈ [−K, K].
In the remaining cases, v has more than two lines, so R and R are in the same rigid component. Height in R is already defined. The same goes for φ(R) and φ(R ). In every case thus far we have produced a universal bound for the height errors of depth zero vertices. The final case is the one to worry about; this is the case where height error can compound. Extend the maps with α = 2 −h(v) and β = 2 −h(φ(v)) . A priori, if v is a depth zero vertex of R we know | Err φ (v ) − Err φ (R )| ≤ K and | Err φ (R) − Err φ (R )| ≤ 2K, so the height errors could be worse than in the previous step. If the errors continue to get worse in each step then we lose control.
However, because we have built according to the set of strategies, we are guaranteed that the height error of R is in [L j , U j ], so Err φ (v ) ∈ [L j − K, U j + K].
This completes the induction steps. The various maps Φ R were constructed so that they agree when they overlap on any depth zero vertex spaces of at least three lines. They may not agree on two-line vertex spaces, but this can be fixed, since two-line patterns are not rigid.
Suppose v is a two-line vertex joining P-sets R and R . Suppose Φ R | Xv is expansion by a factor C, and Φ R | Xv is expansion by a factor C . Change these maps so that they both expand by a factor of C along the lines where the R edges glue on, and expand by a factor of C along the lines where the R edges glue on. This does not change the maps that we had on B(v) ⊂ B(R) and B(v) ⊂ B(R ).
The map Φ is built from various pieces Φ R . The Φ R are bilipschitz bijections on V 0 X R , and agree on vertex spaces where their domains intersect. We have arranged that the bilipschitz constants of Φ R depend on [R] and [φ(R)] and on height error. Tubular groups come from finite graphs of groups, so there are only finitely many equivalence classes of P-set. Thus, invariants of equivalence classes of P-sets can be uniformly bounded. Height error is bounded by The map Φ is thus a bilipschitz bijection Main Theorem. For i = 1, 2, let G i = π 1 (Γ i ) be tubular groups. There is an algorithm that in finite time determines whether or not G 1 and G 2 are quasiisometric.
Proof. Run the algorithm from Theorem 4.5. This algorithm halts in finite time. If the groups are quasi-isometric then Corollary 4.3 and Lemma 4.4 guarantee that the algorithm succeeds and produces a consistent set of strategies. Conversely, Theorem 4.10 builds a quasi-isometry from a consistent set of strategies, so the algorithm succeeds only if the groups are quasi-isometric.

Consequences and Examples
Example 5.1. Consider two tubular groups all of whose depth zero vertices have two lines. The only obstruction to building a quasi-isometry in this case is that P-sets of bounded height change must be matched to P-sets of bounded height change, and similarly for P-sets of unbounded height change.
In particular, we recover the following result of Behrstock and Neumann [1]: Corollary 5.2. Any two Right Angled Artin Groups whose defining graphs are trees of diameter at least three are quasi-isometric.
This follows since such groups have graph of groups decompositions as tubular groups where all depth zero vertices have two lines and all P-sets are of bounded height change.
Suppose G is a tubular group with at least three lines in every vertex and having bounded height change in every P-set. Then there is a notion of height change for every edge in the tree of P-sets.
If γ is a geodesic ray in T G , γ has coarse slope m, slope(γ) = m, if there exists a C > 0 such that for all t, tm − C ≤ h(γ(0), γ(t)) ≤ tm + C Proposition 5.3. There is some m G = max γ⊂T G slope(γ), and the set of slopes of geodesic rays of T G is dense in the interval [−m G , m G ].
Proof. Let γ be a geodesic ray in T G . Consider the image of γ in the graph that is the quotient of T G by the group action. This graph is finite, so the image of γ can be written as some initial segment of bounded length followed by loops in the graph. The initial segment contributes a bounded amount to height, so it can be discarded.
There are only finitely many simple closed curves in a finite graph, so pick one, α, of maximal slope. It is not hard to see that any loop can be reduced to a simple closed curve without reducing slope. Therefore, slope(γ) ≤ slope(α). Then m G = slope(α).
Loops that are homotopically trivial have zero height change, so we can get a geodesic ray in T G of slope arbitrarily close to any m ∈ [−m G , m G ] by concatenating lifts of ±α with lifts of trivial loops.
Corollary 5.4. There is a maximum coarse slope in each rigid component of T G that contains no P-set of unbounded height change.
Suppose G 1 and G 2 are tubular groups with at least three lines in every vertex and having bounded height change in every P-set. Also, suppose that G 1 and G 2 have the same sets of equivalence classes of edge patterns, and that each of these patterns has a unique (up to isometry) symmetric representative. This occurs, for instance, if every vertex has three or four lines.
Suppose m G1 > m G2 , and γ is a geodesic ray of slope m G1 in T G1 . Under a coarsely height preserving tree isomorphism, the image of γ will still be a geodesic ray of slope m G1 , contradicting maximality of m G2 . This means m G is a quasiisometry invariant of G.
When vertices of G have edge patterns without a unique symmetric representative, the value of m G depends on the choice of representatives.
The max slope is not a complete invariant, even among groups from the family described in Section 3.2.5. In Example 5.5 we classify this family completely, and see that groups with the same max slope need not be quasi-isometric. Note. In diagrams of trees of P-sets, P-sets are represented by large open circles labeled by a representative of the equivalence class of P-set. One adjacent vertex is added for each P-set-stabilizer equivalence class of depth zero vertex contained in the P-set, and these are labeled by vertex types with respect to the more heavily shaded P-set in the center of the diagram.
Example 5.5. Suppose G 1 and G 2 are groups as in Figure 2. Each G i has only one equivalence class of P-set, [C i ], and each P-set has three vertex types.  First assume that λ i ≥ µ i ≥ 0. The maximum slope in T i is λ i , so assume that λ = λ 1 = λ 2 . If λ = 0 then there are no height changes to worry about, so the groups are quasi-isometric, so assume λ > 0.
First we attempt to build an extension E = (e jk ) that gives a positive strategy.
To build a consistent set of strategies we will need a positive strategy that gives all non-negative height errors. The largest negative height change that occurs is −λ in both trees, so we must identify these. To accomplish this, e 33 must be nonzero. Furthermore, if we choose this entry to identify the P-sets at height −λ, we are forced to identify P-sets at height −µ 1 with P-sets of height −µ 2 . Thus, we need µ 1 ≤ µ 2 .
We get the reverse inequality by considering a negative strategy. We need a negative strategy that gives all non-positive height errors. The largest positive height change that occurs is λ in both trees, so we must identify these. This forces an identification of P-sets at height λ − µ 1 with P-sets of height λ − µ 2 , so we need µ 1 ≥ µ 2 .
We started by assuming that λ and µ were non-negative. It is not hard to see that groups from this family having pairs of height changes (λ, µ), (λ − µ, −µ) and (−λ, µ − λ) are all quasi-isometric. There is only one distinct such pair with both entries non-negative. Therefore, the (unordered) pair of non-negative height changes gives a complete quasi-isometry invariant for this family. Notice that the max slope is the larger of the two height changes, so we have many examples of groups with the same max slope that are not quasi-isometric.
Finally, we give an example of quasi-isometric groups where there are actually bounded height errors (not always 0 as in Example 5.5) and we really need two distinct strategies for some match.
Let G 2 = π 1 (Γ 2 ) be a tubular group whose underlying graph is shown in Figure 5. In this diagram the labels are height changes and an arc joining edges incident to a common vertex indicates that the corresponding edge strips glue to the vertex space along parallel lines. The Bass-Serre tree, DΓ 2 , has two equivalence classes of P-sets. One class, [A], consists of P-sets that project in Γ 2 to the union of the three edges connected by arcs. The other, [B], consists of P-sets that project to the remaining edge in Γ 2 . Figure 6 and Figure 7 define the vertex types for vertices in A and B, respectively.  Figure 8 shows the result of extending by E A . All the matches induced by this extension have height error 0, so the strategy S A for E A can be used as a positive and a negative strategy.    The extension E − B induces matches ([C], [A]) with height errors 0, −2(λ − µ), λ − µ, so it gives rise to a negative strategy.
These strategies give the set of strategies in Figure 11. This set of strategies gives rise to a system of inequalities: This system has solutions, for instance: Therefore, groups of this form are quasi-isometric.