Metric embeddings and separators for induced-minor-free graphs

For connected graphs excluding the one-subdivision of K_h as an induced minor, seek non-expansive line embeddings with O(log h) average distortion for the stated vertex-weighted metrics and balanced separators of size O(h log h√m) in m-edge graphs.

Why it matters and what counts as progress

Why it matters: It connects a structural graph exclusion to quantitative metric compression and small separators, with sharper dependence on h.

What counts as progress: Improve the dependence on h in average distortion or separator size while retaining the same induced-minor exclusion and weighted metric assumptions.

How the problem developed

2024 · Proof gap reported [1]
Daniel Lokshtanov and collaborators A flaw was identified in a construction used for prior separator results, leaving the induced-minor-free separator claim without that proof.
16 Oct 2026 · Proof [1]
James Davies, Paweł Rzążewski, Jack Spalding-Jamieson and Bartosz Walczak Restored balanced O(√m) separators for graph classes excluding a fixed induced minor and proved associated line-embedding bounds for weighted shortest-path metrics.

AI contribution

Revisiting Separators in String Graphs, Region Intersection Graphs, and Induced-Minor-Free Graphs

James Davies, Paweł Rzążewski, Jack Spalding-Jamieson, Bartosz Walczak

The AI-origin improvement in Appendix B gives non-expansive line embeddings with O(log h) average distortion for the stated vertex-weighted metrics of connected graphs excluding the one-subdivision of K_h as an induced minor. The paper derives balanced separators of size O(h log h √m) for the corresponding m-edge graphs.

AI involvementAI-centered

ImportanceNotable

Technical verificationFormal (Lean)

Human understandingFull