An ancestry labeling scheme labels the nodes of any tree in such a way that ancestry queries between any two nodes in a tree can be answered just by looking at their corresponding labels. The common measure to evaluate the quality of an ancestry labeling scheme is by its label size , that is the maximal number of bits stored in a label, taken over all @math -node trees. The design of ancestry labeling schemes finds applications in XML search engines. In the context of these applications, even small improvements in the label size are important. In fact, the literature about this topic is interested in the exact label size rather than just its order of magnitude. As a result, following the proposal of an original scheme of size @math bits, a considerable amount of work was devoted to improve the bound on the label size. The current state of the art upper bound is @math bits which is still far from the known @math lower bound. Moreover, the hidden constant factor in the additive @math term is large, which makes this term dominate the label size for typical current XML trees. In attempt to provide good performances for real XML data, we rely on the observation that the depth of a typical XML tree is bounded from above by a small constant. Having this in mind, we present an ancestry labeling scheme of size @math , for the family of trees with at most @math nodes and depth at most @math . In addition to our main result, we prove a result that may be of independent interest concerning the existence of a linear universal graph for the family of forests with trees of bounded depth.
@cite_0: How to represent a graph in memory is a fundamental data structuring question. In the usual representations of an n -node graph, the names of the nodes (i.e. integers from 1 to n ) betray nothing about the graph itself. Indeed, the names (or labels) on the n nodes are just log n bit place holders to allow data on the edges to code for the structure of the graph. In our scenario, there is no such waste. By assigning O (log n ) bit labels to the nodes, we completely code for the structure of the graph, so that given the labels of two nodes we can test if they are adjacent in time linear in the size of the labels. Furthermore, given an arbitrary original labeling of the nodes, we can find structure coding labels (as above) that are no more than a small constant factor larger than the original labels. These notions are intimately related to vertex induced universal graphs of polynomial size. For example, we can label planar graphs with structure coding labels of size n . This implies the existence of a graph with n 4 nodes that contains all n -node planar graphs as vertex induced subgraphs (It was not previously known that this class had polynomial sized universal graphs). The theorems on finite graphs extend to a theorem about the constrained labeling of infinite graphs.
@cite_9: We show that there exists a graph G with n spl middot 2 sup O(log* n) nodes, where any forest with n nodes is a node-induced subgraph of G. Furthermore, the result implies the existence of a graph with n sup k 2 sup O(log* n) nodes that contains all n-node graphs of fixed arboricity k as node-induced subgraphs. We provide a lower bound of spl Omega (n sup k ) for the size of such a graph. The upper bound is obtained through a simple labeling scheme for parent queries in rooted trees.
@cite_22: Abstract Abstract Distance hereditary graphs are those graphs for which in any connected induced subgraph, the distance between any two vertices in this subgraph is equal to their distance in the whole graph. This class strictly contains trees. We show how the distance labelling scheme for trees presented in [?] can be extended to distance hereditary graphs with optimal length labels. The result is based on the split decomposition of a graph [?].
@cite_3: Let f be a function on pairs of vertices. An f -labeling scheme for a family of graphs ℱ labels the vertices of all graphs in ℱ such that for every graph G∈ℱ and every two vertices u,v∈G, f(u,v) can be inferred by merely inspecting the labels of u and v. The size of a labeling scheme is the maximum number of bits used in a label of any vertex in any graph in ℱ. This paper illustrates that the notion of universal matrices can be used to efficiently construct f-labeling schemes. Let ℱ(n) be a family of connected graphs of size at most n and let @math denote the collection of graphs of size at most n, such that each graph in @math is composed of a disjoint union of some graphs in ℱ(n). We first investigate methods for translating f-labeling schemes for ℱ(n) to f-labeling schemes for @math . In particular, we show that in many cases, given an f-labeling scheme of size g(n) for a graph family ℱ(n), one can construct an f-labeling scheme of size g(n)+log log n+O(1) for @math . We also show that in several cases, the above mentioned extra additive term of log log n+O(1) is necessary. In addition, we show that the family of n-node graphs which are unions of disjoint circles enjoys an adjacency labeling scheme of size log n+O(1). This illustrates a non-trivial example showing that the above mentioned extra additive term is sometimes not necessary. We then turn to investigate distance labeling schemes on the class of circles of at most n vertices and show an upper bound of 1.5log n+O(1) and a lower bound of 4 3log n−O(1) for the size of any such labeling scheme.
Implicit labeling schemes were first introduced in @cite_0 , where an elegant adjacency labeling schemes of size @math is established on @math -node trees. That paper also notices a relation between adjacency labeling schemes and (see also @cite_9 @cite_22 @cite_3 ). Precisely, it is shown that there exists an adjacency labeling scheme with label size @math for a graph family @math if and only if there exists a universal graph for @math with @math nodes.