STOC Conference 2021 Conference Paper
Optimal labelling schemes for adjacency, comparability, and reachability
- Marthe Bonamy
- Louis Esperet
- Carla Groenland
- Alex D. Scott
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.