The Planar Conjecture on embedding planar graph metrics into \ell_1
A planar graph metric is a shortest-path metric on a finite planar graph whose edges have arbitrary weights. The Planar Conjecture. Every metric supported on a finite planar graph can be embedded into with constant distortion. This is a central open problem in the theory of metric embeddings; the cited work proves the analogous statement for graphs excluding as a minor, with distortion at most , but the planar case remains unresolved.
References
Primary source
Mikhail I. Ostrovskii and Beata Randrianantoanina, “A new approach to low-distortion embeddings of finite metric spaces into non-superreflexive Banach spaces”, arXiv:1609.06618 (2017).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 1
RemarkAI-assistedClaimed by OpenAI. Claims a universal-distortion embedding into real L^1 of every finite connected planar graph's shortest-path metric with arbitrary positive real edge lengths. This is the planar case of the general proper-minor-closed-family conjecture.See full solution
Claimed by OpenAI. Claims a universal-distortion embedding into real L^1 of every finite connected planar graph's shortest-path metric with arbitrary positive real edge lengths. This is the planar case of the general proper-minor-closed-family conjecture.
GitHub repository: https://github.com/openai/math
- OpenAI-089-01-Planar-Graph-Metrics-Embed-into-L1-with-Constant-Distortion.pdfOpen