Tight Quadratic Bound for Facial Distance Patterns in Planar Graphs

In a preprint submitted on August 7, 2026, Viktor Fredslund-Hansen, Shay Mozes, and Oren Weimann prove that an unweighted undirected planar graph has $O(k^2)$ distinct distance patterns with respect to the $k$ vertices of a designated face. This improves the previous $O(k^3)$ upper bound, matches the known quadratic lower bound, and settles a conjecture posed at ISAAC 2022.

The authors report that OpenAI GPT 5.6-Sol found the core proof after receiving a single prompt describing the state of the art and asking for an improvement. Its argument recognized the relevant patterns as weakly separated set systems; the authors then clarified, simplified, and rewrote the proof, including a direct formulation. They also derive improved compression bounds for Okamura--Seymour metrics and exact-distance oracles, as well as a randomized $\widetilde O(n^{8/5})$ algorithm for diameter, radius, and all eccentricities in unweighted undirected planar graphs, improving on the prior $\widetilde O(n^{5/3})$ running time in this setting.