  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 \leq n/5$.
