Short Labels by Traversal and Jumping

In this paper, we propose an efficient implicit representation of caterpillar and bounded degree trees of n vertices. Our scheme, called Traversal & Jumping, assigns to the n vertices of any bounded degree tree distinct binary labels of log 2 n + O ( 1 ) bits in O ( n ) time such that we can compute adjacency between two vertices only from their labels. We use our result to improve previous known upper bound for size of labels of implicit representation of outerplanar graphs (respectively planar graphs) to 2 log 2 n (respectively ( 3 log 2 n )).