Optimal Distance Labeling for Permutation Graphs

Paweł Gawrychowski, Wojciech Janczewski

A permutation graph is the intersection graph of a set of segments between two parallel lines. In other words, they are defined by a permutation $\pi$ on $n$ elements, such that $u$…