What was already known
Li and Parter proved O(k^3); Mozes, Wallheimer and Weimann supplied an Omega(k^2) construction and conjectured the matching upper bound. Existing metric compression, distance-oracle and distributed-diameter bounds used the cubic estimate.
AI involvement
Fredslund-Hansen, Mozes and Weimann gave GPT-5.6 Sol the prior art and asked for an improvement. The model supplied the quadratic bound and proof; the authors clarified it and separately developed the downstream diameter algorithm.
The paper explicitly attributes discovery of the tight bound and short proof to a single model response after the humans stated the task and prior art.
Importance
Matches the known quadratic lower bound and settles the facial-pattern upper-bound conjecture.
Limitations
The bound applies to connected undirected unweighted planar graphs and a designated facial walk. The separate centralized diameter algorithm is human-developed. The paper publishes the proof but does not explicitly document a completed check of it.
Technical verification
Section 2 publishes a full proof and the authors report clarifying and simplifying it, but the reviewed sources do not explicitly document a completed check of the assessed argument. Proof publication and explanation alone do not establish the Formal checking criterion.
Human understanding
The authors explain the cyclic telescoping restriction, the weak-separation connection and the prefix-trie branching count, and state that they simplified the model's proof.
Correction and publication history
Matches the known quadratic lower bound and settles the facial-pattern upper-bound conjecture.
Read this published revision