# springerlink:10.1007/11602613_106

### Summary

**Gavoille, C. and Ly, O.** (2005) *Distance Labeling in Hyperbolic Graphs.* In 16th International Symposium Algorithms and Computation (ISAAC), pages 1071-1079. . Springer Berlin / Heidelberg. ((URL))

### Abstract

A graph {$G$} is {$\delta$}-hyperbolic if for any four vertices {$u , v , x , y$} of {$G$} the two larger of the three distance sums {$d_G( u , v ) + d_G ( x , y ), d_G ( u , x ) + d_G ( v , y ), d_G ( u , y ) + d_G ( v , x )$} differ by at most {$\delta$}, and the smallest {$\delta\geq 0$} for which {$G$} is {$\delta$}-hyperbolic is called the hyperbolicity of {$G$} . In this paper, we construct a distance labeling scheme for bounded hyperbolicity graphs, that is a vertex labeling such that the distance between any two vertices of {$G$} can be estimated from their labels, without any other source of information. More precisely, our scheme assigns labels of {$O(\log^2 n )$} bits for bounded hyperbolicity graphs with n vertices such that distances can be approximated within an additive error of {$O (\log n )$}. The label length is optimal for every additive error up to {$n^\varepsilon$}. We also show a lower bound of {$\Omega(\log\log n )$} on the approximation factor, namely every {$s$}-multiplicative approximate distance labeling scheme on bounded hyperbolicity graphs with polylogarithmic labels requires {$s = \Omega(\log\log n )$}. 11602613_106Bib

### Bibtex entry

`@INCOLLECTION { springerlink:10.1007/11602613_106,`

AUTHOR = { Gavoille, C. and Ly, O. },

AFFILIATION = { LaBRI, Bordeaux University },

TITLE = { Distance Labeling in Hyperbolic Graphs },

BOOKTITLE = { 16th International Symposium Algorithms and Computation (ISAAC) },

SERIES = { Lecture Notes in Computer Science },

EDITOR = { Deng, Xiaotie and Du, Ding-Zhu },

PUBLISHER = { Springer Berlin / Heidelberg },

ISBN = { 978-3-540-30935-2 },

KEYWORD = { Computer Science },

PAGES = { 1071-1079 },

VOLUME = { 3827 },

URL = { http://dx.doi.org/10.1007/11602613_106 },

NOTE = { 10.1007/11602613_106 },

ABSTRACT = { A graph {$G$} is {$\delta$}-hyperbolic if for any four vertices {$u , v , x , y$} of {$G$} the two larger of the three distance sums {$d_G( u , v ) + d_G ( x , y ), d_G ( u , x ) + d_G ( v , y ), d_G ( u , y ) + d_G ( v , x )$} differ by at most {$\delta$}, and the smallest {$\delta\geq 0$} for which {$G$} is {$\delta$}-hyperbolic is called the hyperbolicity of {$G$} . In this paper, we construct a distance labeling scheme for bounded hyperbolicity graphs, that is a vertex labeling such that the distance between any two vertices of {$G$} can be estimated from their labels, without any other source of information. More precisely, our scheme assigns labels of {$O(\log^2 n )$} bits for bounded hyperbolicity graphs with n vertices such that distances can be approximated within an additive error of {$O (\log n )$}. The label length is optimal for every additive error up to {$n^\varepsilon$}. We also show a lower bound of {$\Omega(\log\log n )$} on the approximation factor, namely every {$s$}-multiplicative approximate distance labeling scheme on bounded hyperbolicity graphs with polylogarithmic labels requires {$s = \Omega(\log\log n )$}. },

YEAR = { 2005 },

}