Optimal Distance Labeling for Interval Graphs and Related Graphs Families
Résumé
A distance labeling scheme is a distributed graph representation that assigns labels to the vertices and enables to answer distance queries between any pair (x,y) of vertices by using only the labels of x and y. This paper presents an optimal distance labeling scheme with labels of O(log n) bits for the n-vertex interval graphs family. It improves by log n factor the best known upper bound of [Katz, Katz and Peleg, 2000]. Moreover, the scheme supports constant time distance queries, and if the interval representation of the input graph is given and the intervals sorted, then the set of labels can be computed in O(n) time. Our result is tight as we show that the length of any label is at least 3log n-O(loglog n) bits. This lower bound derives from a new estimator of the number of unlabeled n-vertex interval graphs, that is 2^{\Omega(n log n)}. To our knowledge, interval graphs are thereby the first known non-trivial hereditary family with 2^{\Omega(n f(n))} unlabeled elements and with a distance labeling scheme with f(n) bit labels.