Facial distance-difference patterns in planar graphs
Follow the latest progress by email.
In a connected unweighted undirected planar graph, fix a face whose boundary walk has k edges. How many distinct patterns of consecutive distance differences to that walk can its vertices realize?
Why it matters and what counts as progress
Why it matters: A quadratic rather than cubic pattern bound sharpens the combinatorial input to planar metric compression and distance algorithms.
What counts as progress: An O(k²) upper bound matching the known quadratic constructions, with repeated vertices on the facial walk allowed by the formulation.
How the problem developed
- 2019 · Upper bound [1]
Li and Parter Established an O(k³) upper bound on the number of distinct distance-difference patterns from vertices to a designated facial walk of length k in a planar graph.
- 2022 · Conjecture [1]
Shay Mozes, Boaz Wallheimer and Oren Weimann Recorded the conjectured tight O(k²) bound, matching a known quadratic lower bound, for facial distance patterns.
- 7 Aug 2026 · Tight bound [1]
Viktor Fredslund-Hansen, Shay Mozes and Oren Weimann; GPT-5.6-Sol supplied the bound and proof Proved an O(k²) upper bound matching the lower bound for connected undirected unweighted planar graphs with a designated face.
AI contribution
A Tight Bound for Facial Distance Patterns in Planar Graphs
Fredslund-Hansen, Mozes and Weimann report that, for a connected undirected unweighted planar graph with a designated face whose facial walk has k edges, the number of distinct facial distance-difference patterns is O(k^2), matching the known Omega(k^2) lower bound. The model supplied the forbidden-configuration and fixed-cardinality insight and a short prefix-trie proof; the paper's separate diameter algorithm is human-developed downstream work.
Sources
Website timeline
Publication dates and editorial changes.