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.

Authors

• Marthe Bonamy
• Louis Esperet
• Carla Groenland
• Alex D. Scott

Keywords

• adjacency labelling
• dense graph classes
• graph labelling
• reachability labelling