A subgraph H of a graph G is isometric if the distances between vertices in H coincide with the distances between the corresponding vertices in G. We show that for any integer ngeqslant 1, there is a graph on 3n+O(log2 n) vertices that contains isometric copies of all n-vertex graphs. Our main tool is a new type of distance labelling scheme, whose study might be of independent interest.@en

We construct asymptotically optimal adjacency labelling schemes for every hereditary class containing 2?(n2) n-vertex graphs as n? ?. This regime contains many classes of interest, for instance perfect graphs or comparability graphs, for which we obtain an adjacency labelling scheme with labels of n/4+o(n) bits per vertex. This implies the existence of a reachability labelling scheme for digraphs with labels of n/4+o(n) bits per vertex and comparability labelling scheme for posets with labels of n/4+o(n) bits per element. All these results are best possible, up to the lower order term. @en