Optimal labelling schemes for adjacency, comparability and reachability
share
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 efficient 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) elements, that contains all n-element posets. All these results are best possible, up to the lower order term, and solve several open problems in the area.
READ FULL TEXT