arXiv:2611.11479 · v1

Õptimal Facial Distance Labeling in Planar Graph

首次提交 2026-11-09 00:20

版本更新 2026-11-09 00:20

雷达观测 2026-11-10 12:16

摘要

We show how to assign labels of size $\tilde O(n^{1/3})$ to the vertices of a face $F$ in an $n$-vertex unweighted undirected planar graph $G$ s.t one can deduce the distance between any two vertices of $F$ given their labels alone. This matches (up to log factors) the $Ω(n^{1/3})$ lower bound of Gavoille, Peleg, Pérennes, Raz from 2004. Prior to our work, the smallest labels were of size $O(n^{1/2})$.