Optimal labelling schemes for adjacency, comparability, and reachability

We construct asymptotically optimal adjacency labelling schemes for every hereditary class containing 2 Ω(n 2 ) 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. * M.B. and L.E. are supported by the ANR Projects DISTANCIA (ANR 17 CE40 0015) and GrR (ANR 18 CE40 0032), and by LabEx PERSYVAL-lab (ANR 11 LABX 0025). 1 Throughout the paper, n is implicitly the number of vertices in the graph at hand. 2 Throughout the paper, log n denotes the binary logarithm of n.