这篇把平面图距离模式上界从O(k^3)压到O(k^2)，还顺手改进了直径算法，连GPT-5.6-Sol都参与证明了。
论文针对无向无权平面图，研究顶点到指定面上所有顶点的距离向量模式。作者将Li和Parter在STOC'19给出的O(k^3)上界改进到O(k^2)，匹配已知下界，并解决了ISAAC'22中的猜想。新界直接改进了Okamura-Seymour度量的压缩、常数时间精确距离预言机的空间，以及分布式直径算法。另外还给出集中式O~(n^{8/5})时间直径算法，优于SODA'18的O~(n^{5/3})。简单证明由OpenAI的GPT 5.6-Sol模型发现。
A Tight Bound for Facial Distance Patterns in Planar Graphs
Let $G$ be an undirected unweighted planar graph and let $S=(s_0,\dots,s_{k-1})$ be the vertices of a designated face, listed in cyclic order. Consider a vector that stores the distances from an arbitrary vertex $v$ to all vertices of $S$. The pattern of $v$ is obtained by taking the difference between every pair of consecutive values in this vector. Li and Parter [STOC'19] proved an upper bound of $O(k^3)$ on the number of unique patterns over all vertices of $G$. We improve this to $O(k^2)$, matching a known lower bound and settling a conjecture in [ISAAC'22]. The simple proof was found by OpenAI's GPT 5.6-Sol model. Plugging this new bound into known results has the following three immediate implications for undirected unweighted planar graphs: (1) it gives an improved compression of the Okamura-Seymour metric (2) it improves the space required by constant-time exact distance oracles, and (3) it improves the fastest distributed algorithm for computing the diameter. We further present a previously unknown and nontrivial implication: a (centralized) $\tilde{O}(n^{8/5})$-time algorithm for computing the diameter, improving over the $\tilde{O}(n^{5/3})$ algorithm of [SODA'18] which works for weighted directed planar graphs. Thus, there is currently a gap between the time for computing the diameter between weighted and unweighted planar graphs.