Are there efficient graph partitioning algorithms with guaranteed upper bounds on the bipartition width in terms of the total number of vertices of the graph, or another non-spectral quantity (diameter, girth, ...), for regular graphs?
Most of the bounds I find in the literature are spectral (like Cheeger inequalities and other bounds on the algebraic connectivity). One could combine these bounds with bounds on the spectrum itself, such as the one in this article, to bound something like the sparsest cut, but this approach provides no guarantees with respect to the actual width of the cut (or maybe it does and it is just not clear to me?).
A (loosely) related upper bound is that the bisection width of cubic graphs with $n$ vertices is at most $(\frac16+\epsilon)n, \epsilon>0$ (from this paper). Are there similar worst-case bounds for heuristic bipartition algorithms?