Nearly-Linear Solution to the Word Problem for 3-Manifold Groups

We show that the word problem for any 3-manifold group is solvable in time O(n log³ n). Our main contribution is the proof that the word problem for admissible graphs of groups, in the sense of Croke and Kleiner, is solvable inO(n log n); this covers fundamental groups of non-geometric graph manifolds. Similar methods also give that the word problem for free products can be solved “almost as quickly” as the word problem in the factors.