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
@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 },}