Distance Labeling for Permutation Graphs

We show that every permutation graph with n elements can be preprocessed in O(n) time, if two linear extensions of the corresponding poset are given, to produce an O(n) space data-structure supporting distance queries in constant time. The data-structure is localized and given as a distance labeling, that is each vertex receives a label of O(log n) bits so that distance queries between any two vertices are answered by inspecting on their labels only. This result improves the previous scheme due to Katz, Katz and Peleg [M. Katz, N.A. Katz, and D. Peleg, Distance labeling schemes for well-separated graph classes, in 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS), H. Reichel and S. Tison, eds., vol. 1770 of Lecture Notes in Computer Science, Springer Verlag, Feb. 2000, pp. 516–528] in the STACS ʹ00 by a log n factor.