Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs

1. Introduction

• Fox and Pach proved that string graphs with m edges admit balanced separators of size O(m^(3/4)√log m), and conjectured this could improve to O(√m).The √n × √n grid is planar and does not admit balanced separators of size o(√n).Source: §1 · pp. 1–2
• The paper gives a new proof of the induced-minor separator theorem, thereby proving the string-graph conjecture and fixing the majority of works affected by Lee’s flawed proof [Lee17].Korhonen and Lokshtanov’s broader theorem used an intermediate result of Lee as a black box [KL24].Source: §1 · pp. 2–3
• The proof combines a multicommodity-flow bound yielding value Ω(√m) with a vertex-weighted metric and an embedding into the line.The line-embedding step is where the techniques diverge from Lee’s approach.Source: §1 · p. 3

Padded Decompositions and Metric Embeddings.

• For region intersection graphs over Kh-minor-free graphs, the paper proves padded-decomposition results that in particular give string graphs an (O(1), Ω(1))-padded decomposition scheme.The authors state that the flawed component behind the earlier claim remains without a fix and take a different approach.Source: Padded Decompositions and Metric… · p. 4

Improved Parameter Dependence.

• The improved induced-minor separator theorem has a deterministic polynomial-time algorithm that finds a separator or concludes that the forbidden induced minor occurs.A second Las Vegas randomized polynomial-time algorithm produces an induced-minor model in the latter case.Source: Improved Parameter Dependence · p. 5

Other Related Works.

• The paper notes that constant-factor shortest-path embeddings of unweighted string graphs into planar graphs do not resolve the conjecture, which concerns vertex-weighted metrics.It also states that vertex-weighted string graphs do not admit universally bounded-distortion embeddings into planar graphs.Source: Other Related Works · p. 5

Formalization.

• The existential statements for Theorems 1.3, 1.4, and 1.8 are formalized in Lean 4 with mathlib.The formalization has the same asymptotic dependencies on n, m, and h, though some proof details and constants differ.Source: Formalization · p. 5

2. From Non-Expansive Embeddings to Balanced Separators

• The proof pipeline follows Matoušek’s approach, using two relaxations of a sparsest vertex-cut problem in the style of Leighton and Rao [Mat14].The section identifies a lower bound on Q(G) and a bounded-average-distortion non-expansive embedding as the two steps.Source: §2 · p. 6
• A bounded-average-distortion non-expansive embedding into the line relates the embedding parameter to Q(G), while a lower bound on Q for connected induced subgraphs yields a 2/3-balanced separator.The separator size is at most 4β when every connected induced subgraph H on n′ vertices satisfies Q(H) ≥ (n′)^2/β.Source: §2 · p. 6
• Korhonen and Lokshtanov’s induced-minor criterion supplies a structural step, and failure of its inequality enables a Las Vegas randomized polynomial-time algorithm to find an induced-minor model.The paper notes that their original constant 40 should be 45; it describes this as a minor, fixable issue.Source: §2 · p. 6

3. Main Structural Result

• For endpoint-light vertex-weighted shortest-path metrics, either a large-radius ball or two large separated sets exist, or the graph contains a 1-subdivision of H as an induced minor.The alternatives are stated using thresholds ε and η and distance δ.Source: §3 · p. 7
• Theorem 3.1 is inspired by an induced-subdivision result of Chudnovsky, Scott, Seymour, and Spirkl [CSSS21, 6.4], generalized here to associated metrics and induced minors.The cited result concerns graphs excluding subdivisions of H and their complements as induced subgraphs.Source: §3 · p. 7
• Theorem 3.3 gives a stronger alternative: a large ball, two large separated sets, or a δ-fat model of H in the graph.In a δ-fat model, incident pieces intersect and nonincident pieces are more than δ apart; this result is used to derive Theorem 3.1.Source: §3 · p. 8
• A δ-fat model yields an induced-minor model of the 1-subdivision of H after each edge-piece is replaced by internal vertices of a path between its endpoint-pieces.The conversion uses the bound that every vertex outside the removed set has weight at most δ, so each remaining graph edge has length at most δ.Source: §3 · p. 9
• When the measure is computable in polynomial time, the proof gives a polynomial-time algorithm; for the counting measure, it outputs a large ball, separated large sets, or an induced-minor model.The stated running time is polynomial in |V|.Source: §3 · p. 9

4. Rabinovich Embeddings

• The section identifies non-expansive embeddings with bounded average distortion as its main tool for relating Q(G) quantities.The passage names the quantities but does not specify their definitions here.Source: §4 · p. 9
• For any set S, the map f_S(x) = d(x, S) is a non-expansive embedding into the reals.It assigns each point its distance to the nearest point of S.Source: §4 · p. 9
• The argument treats a large-core case and a well-spread case, corresponding respectively to the first and second outcomes of Theorem 3.4.The well-spread case assumes two disjoint sets of size at least κn separated by a distance threshold.Source: §4 · pp. 9–10

5. Proofs of Main Results

• For graphs excluding K(1) as an induced minor, both endpoint-light and endpoint-heavy vertex-weighted metrics admit non-expansive line embeddings with bounded average distortion.Theorem 1.6 also gives a polynomial-time algorithm that returns an induced-minor model or such an embedding.Source: §5 · p. 10
• The separator proof derives its bound from a lower bound on Q(G) and a non-expansive line embedding with bounded average distortion.The proof sets parameters ε, η, and δ in terms of h and the average pairwise distance.Source: §5 · p. 10
• The endpoint-light metric admits a non-expansive line embedding with average distortion at most 2·52800/169 h^2 < 625h^2.The proof applies two lemmas after separating cases based on ball size or the distance between two large sets.Source: §5 · p. 11
• Theorem 5.2 gives graphs excluding K(1) as an induced minor a balanced separator bound involving √m, with its stated dependence on h and n.The bound is min{O(log n), 35000h^2} · h · √m.Source: §5 · p. 11
• A deterministic polynomial-time algorithm either finds a balanced separator or concludes that the graph contains K(1) as an induced minor.A second Las Vegas randomized polynomial-time algorithm produces an induced-minor model in the latter case.Source: §5 · p. 11

6. Padded Decompositions of Region Intersection Graphs

• A k-dimensional control function ρ ↦ cρ yields a (2c + 2, k + 1)-sparse cover scheme.The construction enlarges partition sets by radius r = ∆/(2c + 2), covering every radius-r ball with bounded overlap.Source: §6 · p. 12
• A (β, s)-sparse cover scheme yields a padded decomposition scheme with parameters determined by β and s.The section combines this implication with the sparse covers obtained from the control functions.Source: §6 · pp. 12, 14
• The two metrics each have Assouad-Nagata dimension at most 2h−2 −1, with respective control functions ρ ↦ (12h −6)ρ and ρ ↦ (16h −8)ρ.Source: §6 · p. 12
• Every string graph admits an (O(1), Ω(1))-padded decomposition scheme.The theorem also gives padded decomposition parameters for the endpoint-light and endpoint-heavy metrics over Kh-minor-free graphs.Source: §6 · pp. 13–14

7. Vertex Expansion, Metric Spread, Balanced Separators, and Relaxations

• If every induced subgraph has vertex expansion at most α, then G admits a 2/3-balanced separator of size at most α.The section also states an algorithmic version when the relevant low-expansion sets can be found efficiently.Source: §7 · p. 14
• If suitable low-expansion sets can be found in time f(n′), a 2/3-balanced separator of size at most α can be found in O(n · f(n)) time.The construction iteratively removes a set and its cover-boundary until at most 2n/3 vertices remain.Source: §7 · p. 14
• The extremal line-embedded spread Q(G) is between n ψ(G) and 4n ψ(G).Here ψ(G) is the cover-vertex expansion defined in the section.Source: §7 · pp. 14–15
• If every connected induced subgraph H with n′ vertices satisfies Q(H) ≥ (n′)^2/β, then G has a 2/3-balanced vertex separator of size at most 4β.The proof uses cover-vertex expansion as an intermediary between Q and vertex separators.Source: §7 · pp. 14–15
• A non-expansive line embedding with average distortion at most α implies α · Q(G) ≥ Q(G).The proof applies the embedding to an optimal solution for Q(G).Source: §7 · p. 16

8. Conclusion: Impact on Previous Works

• The paper reproves the results previously stated by Lee [Lee17] and Korhonen and Lokshtanov [KL24], fixing the majority of papers affected by Lee’s flawed proof.Source: §8 · p. 16

Results Directly Using Separator Theorems.

• Several papers using Lee’s separator theorems as black boxes are now fully fixed; replacing O(√m) with O(√m log m) would typically have made their running times only slightly worse.Source: §8 · p. 16

Results Directly Using Padded Decompositions.

• Theorem 1.4 fixes the uses of Lee’s padded-decomposition result for string graphs in the obstacle-removal work [KLS+22] and the work of Lokshtanov et al. [KLSS21].Source: Results Directly Using Padded… · p. 16
• Lee’s eigenvalue bound is recovered with a weaker bound via Theorem 1.4, while the resulting bound differs by factors depending on h and is O(Δ²) k/|V(G)| when h is constant.Source: Results Directly Using Padded… · p. 16

Results Using Rabinovich Embeddings.

• The missing step in Spalding-Jamieson’s maximally reweighted second-eigenvalue result is fixed by using Rabinovich embeddings instead of padded decompositions.Source: Results Using Rabinovich Embeddings · p. 17

Results Using Klein-Plotkin-Rao Decomposition.

• The string-graph results of Lokshtanov et al. [LPS+24] follow from Theorem 1.4 using unweighted shortest-path metrics, without requiring a string representation.The results also extend to region intersection graphs over Kh-minor-free graphs, while the analogous extension to induced-minor-free graphs remains open.Source: Results Using Klein-Plotkin-Rao… · p. 17

• Davies’s theorem supplies an unweighted planar graph whose shortest-path distances approximate those of the original edge-weighted planar graph.Source: Appendix A · p. 20
• For every D ≥ 1, some vertex-weighted string graph has an endpoint-light shortest-path metric with no embedding of distortion at most D into any edge-weighted planar graph.Source: Appendix A · p. 20
• The contradiction argument transfers a hypothesized planar embedding to an unweighted planar graph, then uses a bounded-radius separator to construct a small grid separator.The resulting grid separator contradicts the lower bound that every balanced separator of the N × N grid has size at least N/3.Source: Appendix A · p. 21
• The same absence of a universal distortion bound holds for endpoint-heavy vertex-weighted shortest-path metrics.Source: Appendix A · p. 21

• Vertex-weighted shortest-path metrics in graphs excluding K(1)_h as an induced minor admit non-expansive line embeddings with average distortion O(log h), or the graph contains that induced minor.Source: Appendix B · p. 21
• A polynomial-time algorithm either finds the induced-minor model or produces the non-expansive line embedding.Source: Appendix B · p. 21
• The improved embedding bound has best-possible dependence on h, as realized by expanders.Source: Appendix B · p. 21
• The appendix restates a balanced-separator result for m-edge graphs excluding K(1)_h as an induced minor, with a deterministic polynomial-time algorithm that either finds a separator or reports the induced minor.Source: Appendix B · p. 22
• The embedding proof repeatedly applies a theorem to shrinking terminal sets through metric peeling, then applies a final lemma to the residual terminals and peeled vertices.Source: Appendix B · p. 22