Applying clique-decomposition for computing Gromov hyperbolicity

Description

The shortest-path metric d of a connected graph G is δ-hyperbolic if, and only if, it satisfies d(u, v)+d(x, y) ≤ max{d(u, x)+d(v, y), d(u, y)+d(v, x)}+2δ, for every 4-tuple u, x, v, y of G. We investigate some relations between the hyperbolicity of a graph and the hyperbolicity of its atoms, that are the subgraphs resulting from the clique-decomposition invented by Tarjan [34, 45]. More precisely, we prove that the maximum hyperbolicity taken over all the atoms is at least the hyperbolicity of G minus one. We also give an algorithm to slightly modify the atoms, which is at no extra cost than computing the atoms themselves, and so that the maximum hyperbolicity taken over all the resulting graphs is exactly the hyperbolicity of G. An experimental evaluation of our methodology is provided for large collaboration networks. Finally, we deduce from our theoretical results the first linear-time algorithm to compute the hyperbolicity of an outerplanar graph.

Abstract (French)

La métrique d des plus courts chemins d'un graphe connexe G est δ-hyperbolique si, et seulement si, elle satisfait d(u, v) + d(x, y) ≤ max{d(u, x) + d(v, y), d(u, y) + d(v, x)} + 2δ, pour tout quadruplet u, x, v, y de G. Nous étudions la relation entre l'hyperbolicité d'un graphe et celle de chacun de ses atomes. Ces derniers sont les sous-graphes résultant de la décomposition d'un graphe par des cliques-séparatrices [34, 45]. Plus précisemment, nous montrons que l'hyperbolicité d'un atome est au plus l'hyperbolicité de G moins un. Nous proposons un algorithme pour modifier les atomes de sorte que la valeur maximale de l'hyperbolicité de ces atomes modifiés soit exactement l'hyperbolicité de G. La complexité de cet algorithme est la même que celle de la décomposition du graphe par des cliques-séparatrices. Nous évaluons expériementalement cette méthode sur des graphes de collaborations (co-auteurs). Enfin, nous proposons un algorithme pour calculer en temps linéaire l'hyperbolicité des graphes planaires extérieurs.

Additional details