We construct asymptotically optimal adjacency labelling schemes for every hereditary class containing 2^{\Omega(n^2)} n-vertex graphs as n\to \infty. 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 . We also use this result to construct a poset on 2^{n/4+o(n) . All these results are best possible, up to the lower order term , and solve several open problems in the area .
We construct asymptotically optimal adjacency labelling schemes for every hereditary class containing 2^{\Omega(n^2)} n-vertex graphs as n\to \infty. 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 .
R
. We also use this result to construct a poset on 2^{n/4+o(n)
and comparability labelling scheme for posets with labels of n/4+o(n) bits per element
D
, and solve several open problems in the area