Distance labeling schemes for K4-free bridged graphs

-Approximate distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the -approximation of the distance between any two vertices and can be determined efficiently by merely inspecting the labels of and , without using any other information. One of the important problems is finding natural classes of graphs admitting exact or approximate distance labeling schemes with labels of polylogarithmic size. In this paper, we describe a 4-approximate distance labeling scheme for the class of -free bridged graphs. This scheme uses labels of poly-logarithmic length allowing a constant decoding time. Given the labels of two vertices and , the decoding function returns a value between the exact distance and its quadruple .