provide a tighter multiplicative girth approximation and multiplicative spanner stretch in the same runtime as the algorithms in [@PRSTV18], which produce a $O(k \log n)$ girth approximation and $O(k\log n)$ roundtrip spanner with $\tilde{O}(n^{1 + 1/k})$ edges in time $\tilde{O}(m^{1 + 1/k}).$

Additionally, our algorithm is deterministic and in our opinion, simpler. The algorithm of Pachocki [*et al.*]{} [@PRSTV18] involved the following pieces. First, they use a method of Cohen to estimate ball sizes [@Cohen97] and resolve the case where there is a vertex whose inball and outball (of some small radius) intersect in a significant fraction of the vertices. In the other case, they use exponential clustering (see [@MPX13]) to partition the graph and recurse. Finally, they rerun the algorithm $n^{1/k}$ times. On the other hand, our algorithm simply grows inballs and outballs from various vertices, and uses a delicate cutting conditition to decide when to cut and recurse.

Additionally, \[thm:const\_girth\] and \[thm:arb\_const\_spanner\] further improve upon Pachocki [*et al.*]{} [@PRSTV18] by combining the ideas from the constant factor girth approximation algorithm and the deterministic ball-growing algorithm, completely removing the dependence on $n$ in the approximation factor while still running in time ${\tilde{O}}(m^{1+1/k})$. We remark that the ideas for our 