  Distance labeling schemes are schemes that label the vertices of a graph with
short labels in such a way that the distance between any two vertices $u$ and
$v$ can be determined efficiently by merely inspecting the labels of $u$ and
$v$, without using any other information. Similarly, routing labeling schemes
label the vertices of a graph in a such a way that given the labels of a source
node and a destination node, it is possible to compute efficiently the port
number of the edge from the source that heads in the direction of the
destination. One of important problems is finding natural classes of graphs
admitting distance and/or routing labeling schemes with labels of
polylogarithmic size. In this paper, we show that the class of cube-free median
graphs on $n$ nodes enjoys distance and routing labeling schemes with labels of
$O(\log^3 n)$ bits.
