In this paper we define the notion of $(p,\delta)$--Gromov hyperbolic space where we relax Gromov's { \it slimness} condition to allow that not all but a positive fraction of all triangles are $\delta$--slim. Furthermore, we study maximum vertex congestion under geodesic routing and show that it scales as $\Omega(p^2n^2/D_n^2)$ where $D_n$ is the diameter of the graph. We also construct a constant degree family of expanders with congestion $\Theta(n^2)$ in contrast with random regular graphs that have congestion $O(n\log^{ 3}(n))$. Finally, we study traffic congestion on graphs defined as product of trees.
Categories: math.CO cs.DM cs.NI