Labeling Schemes for Bounded Degree Graphs

David Adjiashvili, Noy Rotbart

We investigate adjacency labeling schemes for graphs of bounded degree $\Delta =O(1)$. In particular, we present an optimal (up to an additive constant) $\log n+O(1)$ adjacency labeli…