The GNRS conjecture on graph families and minor exclusion
The GNRS conjecture on graph families and minor exclusion
For a graph family , let denote the supremum of the least distortion needed to embed its members into .
GNRS conjecture. For every family of finite graphs , one has if and only if forbids some minor.
The conjecture would characterize graph families with uniformly bounded -embedding distortion, equivalently those with uniformly bounded multi-commodity flow/cut gap. It generalizes the planar embedding problem and remains open.
Sources & referencesView supporting material
Primary source
Anastasios Sidiropoulos, “Non-positive curvature, and the planar embedding conjecture”, arXiv:1304.7512 (2013).
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 0
Sign in to submit a solution.
No solutions have been posted yet.