Labeling Schemes for Bounded Degree Graphs

Abstract

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 labeling scheme for bounded degree trees. The latter scheme is derived from a labeling scheme for bounded degree outerplanar graphs. Our results complement a similar bound recently obtained for bounded depth trees [Fraigniaud and Korman, SODA 10], and may provide new insights for closing the long standing gap for adjacency in trees [Alstrup and Rauhe, FOCS 02]. We also provide improved labeling schemes for bounded degree planar graphs. Finally, we use combinatorial number systems and present an improved adjacency labeling schemes for graphs of bounded degree $\Delta$ with $(e+1)\sqrt{n}<\Delta \le n/5$.