pipette
ESEspañol

\~Optimal Facial Distance Labeling in Planar Graph

Noy Rotbart, Oren Weimann

Preprint

In the authors' words

We show how to assign labels of size to the vertices of a face in an -vertex unweighted undirected planar graph s.t one can deduce the distance between any two vertices of given their labels alone. This matches (up to log factors) the lower bound of Gavoille, Peleg, P\'erennes, Raz from 2004. Prior to our work, the smallest labels were of size .

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.