pith. machine review for the scientific record. sign in

arxiv: 2604.07903 · v1 · submitted 2026-04-09 · 🧮 math.CO · cs.DM

Recognition: no theorem link

Sparse String Graphs and Region Intersection Graphs over Minor-Closed Classes have Linear Expansion

David R. Wood, Nikolai Karol

Authors on Pith no claims yet

Pith reviewed 2026-05-10 17:52 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords string graphsregion intersection graphsminor-closed classeslinear expansiongraph separatorsgraph coloring
0
0 comments X

The pith

Sparse string graphs on a fixed surface have linear expansion, extending to sparse region intersection graphs over any proper minor-closed class.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets out to prove that string graphs formed by curves on any fixed surface, provided they have bounded average degree, must satisfy linear expansion. This means the boundary of every small vertex set is at least a positive constant times the size of the set. A reader would care because the property forces good separators and controls global connectivity in geometrically constrained graphs. The authors extend the claim to intersection graphs of regions whose underlying structures belong to any fixed proper minor-closed class. They obtain the expansion bounds combinatorially and note direct consequences for coloring these graphs.

Core claim

We prove that sparse string graphs in a fixed surface have linear expansion. We extend this result to the more general setting of sparse region intersection graphs over any proper minor-closed class. The proofs are combinatorial and self-contained, and provide bounds that are within a constant factor of optimal.

What carries the argument

Linear expansion of the intersection graph, obtained by counting forced intersections or crossings in the geometric representation on the surface or in the minor-closed class.

Load-bearing premise

The graphs must have bounded average degree and the surface or minor-closed class must be fixed.

What would settle it

A family of bounded-degree string graphs on a single fixed surface in which some sequence of sets S has boundary size o(|S|) would falsify the claim.

Figures

Figures reproduced from arXiv: 2604.07903 by David R. Wood, Nikolai Karol.

Figure 1
Figure 1. Figure 1: A junction in J ′ : a pair of edges (a, b) ∈ E(G⃗ ) and ij ∈ E(J ′ ) such that b ∈ Qij and a ∈ Sℓ . The vertices i, j, ℓ ∈ V (J ′ ) are distinct. 5 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Qij is the path that consists of the concatenation of Pi,j , the edge xy, and Pj,i. Observe that for any subgraph J ′ of J, (Si : i ∈ V (J ′ )) is a model of J ′ in G, and (Qij : ij ∈ E(J ′ )) properly represents (Si : i ∈ V (J ′ )). Lemma 9. Let G be a region intersection graph over a graph H, J be a minor of G, and (Si : i ∈ V (J)) be a model of J in G. Let (Qij : ij ∈ E(J)) be a collection of paths that… view at source ↗
Figure 3
Figure 3. Figure 3: Construction of Bi,j in Case 1. The vertices of Bi,j are green. An edge of H between Bi,j and V (Ay) is red. Recall the choice of x and y in the corresponding Case 1 in the definition of Qij and the notation of α. Since distG[Si] (ci , x) = α, we have ( S t∈Pi,j\{x} V (At)) ∩ S r∈Sj V (Ar) = ∅. Since distAx (Ax ∩ Ax↑ , Ax ∩ Ay) is minimised, no vertex of the shortest path in Ax between V (Ax) ∩ V (Ax↑ ) an… view at source ↗
Figure 4
Figure 4. Figure 4: Construction of Bj,i in Case B. The vertices of Bj,i are green. The vertices of Bi are red. An edge of H between Bi and Bj,i is orange. Observe that in each case, V (Acj ) ⊆ Bj,i, and Bj,i ⊆ S t∈Pj,i V (At), and H[Bj,i] is connected. Claim 9.3. For each edge ij ∈ E(J ∗ ) such that i < j, we have Bj,i ∩ Bi = ∅, and there is an edge of H between Bj,i and Bi. Proof. In Case B, both properties immediately foll… view at source ↗
Figure 5
Figure 5. Figure 5: Construction in the proof of Proposition [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
read the original abstract

We prove that sparse string graphs in a fixed surface have linear expansion. We extend this result to the more general setting of sparse region intersection graphs over any proper minor-closed class. The proofs are combinatorial and self-contained, and provide bounds that are within a constant factor of optimal. Applications of our results to graph colouring are presented.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper proves that sparse string graphs (with bounded average degree) embedded in a fixed surface have linear expansion, with bounds within a constant factor of optimal. It extends the result combinatorially to sparse region intersection graphs over any proper minor-closed class. The proofs are presented as self-contained and combinatorial, without external parameters, and applications to graph colouring are included.

Significance. If the claims hold, the result strengthens the structural theory of string graphs and intersection graphs in minor-closed families by establishing linear expansion, which has direct implications for separators, colouring, and algorithmic properties. The self-contained combinatorial proofs and near-optimal constants are notable strengths, as they avoid reliance on fitted parameters or prior results and provide falsifiable, explicit bounds.

minor comments (3)
  1. [Abstract] Abstract: the phrase 'within a constant factor of optimal' is used without specifying the optimal expansion function or the dependence on the fixed surface/genus; a brief parenthetical or reference to the main theorem would improve precision.
  2. [Introduction] Introduction (likely §1): the definition of 'sparse' as bounded average degree is stated but the precise bound (e.g., average degree ≤ d for fixed d) and how it interacts with the surface or minor-closed class could be stated more explicitly at the outset.
  3. [Applications section] The applications to graph colouring are mentioned but not quantified; if the colouring consequences follow directly from the expansion, a short corollary or reference to the implied chromatic number bound would strengthen the presentation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading and positive assessment of the manuscript. The report recommends minor revision but does not raise any specific major comments or points requiring clarification, correction, or additional argument. We therefore have no individual referee comments to address point by point.

Circularity Check

0 steps flagged

No significant circularity; proofs are self-contained combinatorial arguments

full rationale

The paper's central claims rest on explicit combinatorial definitions of sparsity (bounded average degree) and proper minor-closed classes, with proofs presented as self-contained and independent of any fitted parameters or prior self-citations that would reduce the linear expansion result to a tautology by construction. No self-definitional steps, fitted-input predictions, or load-bearing uniqueness theorems imported from the authors' own work appear in the derivation chain. The extension from string graphs on surfaces to region intersection graphs relies on standard preservation properties of minor-closed families, which are externally verifiable and not derived from the target theorem itself. This matches the default expectation for a combinatorial graph theory paper whose arguments do not collapse to their inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Only the abstract is available, so the ledger is inferred from standard assumptions in combinatorial graph theory papers on string graphs and minor-closed classes. No free parameters or invented entities are indicated.

axioms (2)
  • standard math Standard definitions of string graphs, region intersection graphs, sparsity (bounded average degree), and proper minor-closed classes hold.
    Invoked implicitly in the statement of the theorems.
  • domain assumption Linear expansion is defined via the existence of linear-size separators in every subgraph.
    Central to the claim but not derived in the abstract.

pith-pipeline@v0.9.0 · 5336 in / 1170 out tokens · 22688 ms · 2026-05-10T17:52:36.409993+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

54 extracted references · 7 canonical work pages

  1. [1]

    On grids in topological graphs

    Eyal Ackerman, Jacob Fox, János Pach, and Andrew Suk. On grids in topological graphs. Comput. Geom., 47(7):710–723, 2014

    2014

  2. [2]

    Sang Won Bae, Jean-François Baffier, Jinhee Chun, Peter Eades, Kord Eickmeyer, Luca Grilli, Seok-Hee Hong, Matias Korman, F abrizio Montecchiani, Ignaz Rutter, and Csaba D. Tóth. Gap-planar graphs.Theor. Comput. Sci., 745:36–52, 2018

    2018

  3. [3]

    On the topology of the genetic fine structure.Proceedings of the National Academy of Sciences, 45(11):1607–1620, 1959

    Seymour Benzer. On the topology of the genetic fine structure.Proceedings of the National Academy of Sciences, 45(11):1607–1620, 1959

    1959

  4. [4]

    Chang, J

    Hsien-Chih Chang, Jonathan Conroy, Zihan Tan, and Da Wei Zheng. O(1)-distortion planar emulators for string graphs. 2025, arXiv:2510.21700

    work page arXiv 2025

  5. [5]

    Degree-3 treewidth sparsifiers

    Chandra Chekuri and Julia Chuzhoy. Degree-3 treewidth sparsifiers. InPiotr Indyk, ed., Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms(SODA 2015), pp. 242–255. SIAM, 2015

    2015

  6. [6]

    Guantao Chen and Richard H. Schelp. Graphs with linearly bounded Ramsey numbers.J. Combin. Theory Ser. B, 57(1):138–149, 1993. [7]James Da vies. String graphs are quasi-isometric to planar graphs. 2025, arXiv:2510.19602

    work page arXiv 1993

  7. [7]

    Vida Dujmović, Pat Morin, and Da vid R. Wood. Layered separators in minor-closed graph classes with applications.J. Combin. Theory Ser. B, 127:111–147, 2017. arXiv:1306.1595

    work page arXiv 2017

  8. [8]

    Constant-factor approximation of the domination number in sparse graphs

    Zdeněk Dvořák. Constant-factor approximation of the domination number in sparse graphs. European J. Comb., 34(5):833–840, 2013

    2013

  9. [9]

    Sublinear separators, fragility and subexponential expansion.European J

    Zdeněk Dvořák. Sublinear separators, fragility and subexponential expansion.European J. Combin., 52(A):103–119, 2016

    2016

  10. [10]

    Strongly sublinear separators and polynomial expansion

    Zdeněk Dvořák and Sergey Norin. Strongly sublinear separators and polynomial expansion. SIAM J. Discrete Math., 30(2):1095–1101, 2016

    2016

  11. [11]

    On classes of graphs with strongly sublinear separators.European J

    Zdeněk Dvořák. On classes of graphs with strongly sublinear separators.European J. Combin., 71:1–11, 2018

    2018

  12. [12]

    A note on sublinear separators and expansion.European J

    Zdeněk Dvořák. A note on sublinear separators and expansion.European J. Combin., 93:103273, 2021

    2021

  13. [13]

    Intersection graphs of curves in the plane.J

    Gideon Ehrlich, Shimon Even, and Robert Endre Tarjan. Intersection graphs of curves in the plane.J. Combin. Theory Ser. B, 21(1):8–20, 1976

    1976

  14. [14]

    Crossing patterns in nonplanar road networks

    Da vid Eppstein and Siddharth Gupta. Crossing patterns in nonplanar road networks. In Proc. 25th ACM SIGSPATIAL Int’l Conf. on Advances in Geographic Information Systems, pp. 40:1–9. 2017

    2017

  15. [15]

    Polynomial expansion and sublinear separators

    Louis Esperet and Jean-Florent Raymond. Polynomial expansion and sublinear separators. European J. Combin., 69:49–53, 2018

    2018

  16. [16]

    A separator theorem for string graphs and its applications.Combin

    Jacob Fox and János Pach. A separator theorem for string graphs and its applications.Combin. Probab. Comput., 19(3):371–390, 2010

    2010

  17. [17]

    String graphs and incomparability graphs.Adv

    Jacob Fox and János Pach. String graphs and incomparability graphs.Adv. Math., 230(3):1381– 1401, 2012

    2012

  18. [18]

    Applications of a new separator theorem for string graphs.Combin

    Jacob Fox and János Pach. Applications of a new separator theorem for string graphs.Combin. Probab. Comput., 23(1):66–74, 2014

    2014

  19. [19]

    Coloring and covering nowhere dense graphs.SIAM J

    Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos Sta vropoulos. Coloring and covering nowhere dense graphs.SIAM J. Discrete Math., 32(4):2467–2481, 2018

    2018

  20. [20]

    Deciding first-order properties of nowhere dense graphs.J

    Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs.J. ACM, 64(3):Art. 17, 2017

    2017

  21. [21]

    Louis Hakimi

    S. Louis Hakimi. On the degrees of the vertices of a directed graph.J. Franklin Inst., 279:290–308, 1965

    1965

  22. [22]

    Har vey and Da vid R

    Daniel J. Har vey and Da vid R. Wood. Parameters tied to treewidth.J. Graph Theory, 84(4):364–385, 2017

    2017

  23. [23]

    Kevin Hendrey, Nikolai Karol, and Da vid R. Wood. Structure of k-matching-planar graphs. 2025, arXiv:2507.22395. 19

    work page arXiv 2025

  24. [24]

    String graphs: product structure and localised representations

    Nikolai Karol. String graphs: product structure and localised representations. 2025, arXiv:2511.15156

    work page arXiv 2025

  25. [25]

    Kierstead and William T

    Hal A. Kierstead and William T. Trotter. Planar graph coloring with an uncooperative partner.J. Graph Theory, 18(6):569–584, 1994

    1994

  26. [26]

    Kierstead and Daqing Yang

    Hal A. Kierstead and Daqing Yang. Orderings on graphs and game coloring number.Order, 20(3):255–264, 2003

    2003

  27. [27]

    Kleitman

    Daniel J. Kleitman. The crossing number ofK5,n.J. Combinatorial Theory, 9:315–323, 1970

    1970

  28. [28]

    Kostochka

    Alexandr V. Kostochka. The minimum Hadwiger number for graphs with a given mean degree of vertices.Metody Diskret. Analiz., 38:37–58, 1982

    1982

  29. [29]

    Kostochka

    Alexandr V. Kostochka. Lower bound of the Hadwiger number of graphs by their average degree.Combinatorica, 4(4):307–316, 1984

    1984

  30. [30]

    Kostochka, Éric Sopena, and Xuding Zhu

    Alexandr V. Kostochka, Éric Sopena, and Xuding Zhu. Acyclic and oriented chromatic numbers of graphs.J. Graph Theory, 24(4):331–340, 1997

    1997

  31. [31]

    String graphs

    Jan Kratochvíl. String graphs. I. The number of critical nonstring graphs is infinite.J. Combin. Theory Ser. B, 52(1):53–66, 1991

    1991

  32. [32]

    String graphs

    Jan Kratochvíl. String graphs. II. Recognizing string graphs is NP-hard.J. Combin. Theory Ser. B, 52(1):67–78, 1991

    1991

  33. [33]

    String graphs requiring exponential representations.J

    Jan Kratochvíl and Jirí Matousek. String graphs requiring exponential representations.J. Combin. Theory Ser. B, 53(1):1–4, 1991

    1991

  34. [34]

    James R. Lee. Separators in region intersection graphs. InChristos H. Papadimitriou, ed., Proc. 8th Innovations in Theoretical Computer Science Conference, vol. 67 ofLIPIcs, pp. 1:1–1:8. Schloss Dagstuhl, 2017. arXiv:1608.01612

    work page arXiv 2017

  35. [35]

    Near-optimal separators in string graphs.Combin

    Jiří Matoušek. Near-optimal separators in string graphs.Combin. Probab. Comput., 23(1):135– 139, 2014

    2014

  36. [36]

    String graphs and separators

    Jiří Matoušek. String graphs and separators. InGeometry, structure and randomness in combinatorics, vol. 18 ofCRM Series, pp. 61–97. Ed. Norm., Pisa, 2015

    2015

  37. [37]

    Intersection graphs with and without product structure

    Laura Merker, Lena Scherzer, Samuel Schneider, and Torsten Ueckerdt. Intersection graphs with and without product structure. InStef an Felsner and Karsten Klein, eds., Proc. 32nd International Symposium on Graph Drawing and Network Visualization(GD 2024), vol. 320 ofLIPIcs, pp. 23:1–23:19. Schloss Dagstuhl, 2024

    2024

  38. [38]

    Sparsity, vol

    Jarosla v Nešetřil and Patrice Ossona de Mendez. Sparsity, vol. 28 ofAlgorithms and Combinatorics. Springer, 2012

    2012

  39. [39]

    Proper minor-closed families are small.J

    Serguei Norine, Paul Seymour, Robin Thomas, and Paul Wollan. Proper minor-closed families are small.J. Combin. Theory Ser. B, 96(5):754–757, 2006

    2006

  40. [40]

    Patrice Ossona de Mendez, Sang-il Oum, and Da vid R. Wood. Defective colouring of graphs excluding a subgraph or minor.Combinatorica, 39(2):377–410, 2019

    2019

  41. [41]

    Reed, and Yelena Yuditsky

    János Pach, Bruce A. Reed, and Yelena Yuditsky. Almost all string graphs are intersection graphs of plane convex sets.Discret. Comput. Geom., 63(4):888–917, 2020

    2020

  42. [42]

    How many ways can one draw a graph?Combinatorica, 26(5):559–576, 2006

    János Pach and Géza Tóth. How many ways can one draw a graph?Combinatorica, 26(5):559–576, 2006

    2006

  43. [43]

    Trotter, and Bartosz W alczak

    Arkadiusz Pa wlik, Jakub Kozik, Tomasz Kra wczyk, Michał Lasoń, Piotr Micek, William T. Trotter, and Bartosz W alczak. Triangle-free intersection graphs of line segments with large chromatic number.J. Combin. Theory Ser. B, 105:6–10, 2014

    2014

  44. [44]

    Serge Plotkin, Satish Rao, and W arren D. Smith. Shallow excluded minors and improved graph decompositions. InDaniel Sleator, ed.,Proc. 5th Annual ACM-SIAM Symp. Discrete Algorithms(SODA ’94), pp. 462–470. ACM, 1994

    1994

  45. [45]

    Recognizing string graphs in NP.J

    Marcus Schaefer, Eric Sedgwick, and Daniel Štef ankovič. Recognizing string graphs in NP.J. Comput. System Sci., 67(2):365–380, 2003

    2003

  46. [46]

    Decidability of string graphs.J

    Marcus Schaefer and Daniel Štef ankovič. Decidability of string graphs.J. Comput. System Sci., 68(2):319–334, 2004

    2004

  47. [47]

    Small complete minors above the extremal edge density

    Asaf Shapira and Benny Sudakov. Small complete minors above the extremal edge density. Combinatorica, 35(1):75–94, 2015. 20

    2015

  48. [48]

    The Clarkson-Shor technique revisited and extended.Combin

    Micha Sharir. The Clarkson-Shor technique revisited and extended.Combin. Probab. Comput., 12(2):191–201, 2003

    2003

  49. [49]

    On the generalized coloring numbers.Comput

    Sebastian Siebertz. On the generalized coloring numbers.Comput. Sci. Rev., 59:100855, 2026

    2026

  50. [50]

    Frank W. Sinden. Topology of thin film RC circuits.Bell System Technical Journal, 45(9):1639– 1662, 1966

    1966

  51. [51]

    An extremal function for contractions of graphs.Math

    Andrew Thomason. An extremal function for contractions of graphs.Math. Proc. Cambridge Philos. Soc., 95(2):261–265, 1984

    1984

  52. [52]

    The extremal function for complete minors.J

    Andrew Thomason. The extremal function for complete minors.J. Combin. Theory Ser. B, 81(2):318–338, 2001

    2001

  53. [53]

    String graphs have the Erdős–Hajnal property.J

    István Tomon. String graphs have the Erdős–Hajnal property.J. European Math. Soc., 26(1):275– 287, 2024. [55]Da vid R. Wood. Expansion of gap-planar graphs. 2025, arXiv:2509.03121

    work page arXiv 2024

  54. [54]

    Colouring graphs with bounded generalized colouring number.Discrete Math., 309(18):5562–5568, 2009

    Xuding Zhu. Colouring graphs with bounded generalized colouring number.Discrete Math., 309(18):5562–5568, 2009. 21

    2009