Labeling Schemes for Tree Representation

International audienceThis paper deals with compact label-based representations for trees. Consider an $n$-node undirected connected graph $G$ with a predefined numbering on the ports of each node. The {\em all-ports} tree labeling $\cL_{all}$ gives each node $v$ of $G$ a label containing the port numbers of all the {\em tree} edges incident to $v$. The {\em upward} tree labeling $\cL_{up}$ labels each node $v$ by the number of the port leading from $v$ to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted $M_{up}(T)$ and $S_{up}(T)$ for $\cL_{up}$ and $M_{all}(T)$ and $S_{all}(T)$ for $\cL_{all}$. The problem studied in this paper is the following: Given a graph $G$ and a predefined port labeling for it, with the ports of each node $v$ numbered by $0,\ldots,\deg(v)-1$, select a rooted spanning tree for $G$ minimizing (one of) these measures. We show that the problem is polynomial for $M_{up}(T)$, $S_{up}(T)$ and $S_{all}(T)$ but NP-hard for $M_{all}(T)$ (even for 3-regular planar graphs). We show that for every graph $G$ and port numbering there exists a spanning tree $T$ for which $S_{up}(T) = O(n\log\log n)$. We give a tight bound of $O(n)$ in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port assignments. We conclude by discussing some applications for our tree representation schemes