Labeling schemes for trees and planar graphs

18/05/2017 - 12:00

Labeling schemes seek to assign a label to each node in a network, so that a function on two nodes can be computed by examining their labels alone. The goal is to minimize the maximum length of a label and (as a secondary goal) the time to evaluate the function. As a prime example, we might want to compute the distance between two nodes of a network using only their labels. We consider this question for two natural classes of networks: trees and planar graphs. For trees on n nodes, we
design labels consisting of 1/4log^2(n) bits (up to lower order terms), thus matching a recent lower bound of Alstrup et al. [ICALP 2016]. For planar graphs, the situation is much more complex. A major open problem is to close the gap between an upper bound of O(n^{1/2}log(n))-bits and a lower bound of O(n^{1/3})-bits for unweighted planar graphs. We show that, for undirected unweighted planar graphs, there is no hope to achieve a higher lower bound using the known techniques. This is done by designing a centralized structure of size ~O(min(k^2,(kn)^{1/2})) that can calculate the distance between any pair of designated k terminal nodes. We show that this size it tight, up to polylogarithmic terms, for such centralized structures. This is complemented by an improved upper bound of O(n^{1/2}) for labeling nodes of an undirected unweighted planar graph for calculating the distances.