\~Optimal Facial Distance Labeling in Planar Graph
En palabras de los autores
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 .
Resultado principalEl resumen no menciona limitaciones.
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.