Let $G$ be an undirected unweighted planar graph and let $S=(s_0,\dots,s_{k-1})$ denote the vertices of a designated face in cyclic order. For any vertex $v$, form the distance vector $d_v$ to all vertices of $S$ and take the difference between consecutive entries to obtain the pattern $p(v)$. Li and Parter [STOC'19] proved an upper bound of $O(k^3)$ on the number of distinct patterns over all vertices. Using a concise proof discovered by OpenAI's GPT 5.6‑Sol model, we improve this bound to $O(k^2)$, which matches the known lower bound and settles the conjecture from [ISAAC'22].
Plugging the new bound into existing frameworks yields three immediate implications: (1) an improved compression scheme for the Okamura‑Seymour metric; (2) reduced space for constant‑time exact distance oracles; (3) a faster distributed algorithm for computing the diameter.
Moreover, we uncover a previously unknown non‑trivial consequence: a centralized algorithm that computes the diameter of an unweighted planar graph in $\tilde{O}(n^{8/5})$ time, improving over the $\tilde{O}(n^{5/3})$ algorithm of [SODA'18] for weighted directed planar graphs. This highlights a current gap between the diameter‑computation complexities for weighted versus unweighted planar graphs.
Blogger's Review: The paper not only tightens the theoretical bound for facial distance patterns but also translates this improvement into concrete algorithmic gains, making the result both elegant and practically impactful.