Product Structure of Graph Classes with Strongly Sublinear Separators
Dvořák, Zdeněk1; Wood, David R.2
1 Institute of Computer Science Charles University Prague, Czech Republic
2 School of Mathematics Monash University Melbourne, Australia
Innovations in Graph Theory, Volume 2 (2025), pp. 191-222.

We investigate the product structure of hereditary graph classes admitting strongly sublinear separators. We characterise such classes as subgraphs of the strong product of a star and a complete graph of strongly sublinear size. In a more precise result, we show that if any hereditary graph class $\mathcal{G}$ admits $O(n^{1-\epsilon })$ separators, then for any fixed $\delta \in (0,\epsilon )$ every $n$-vertex graph in $\mathcal{G}$ is a subgraph of the strong product of a graph $H$ with bounded tree-depth and a complete graph of size $O(n^{1-\epsilon +\delta })$. This result holds with $\delta =0$ if we allow $H$ to have tree-depth $O(\log \log n)$. Moreover, using extensions of classical isoperimetric inequalties for grids graphs, we show the dependence on $\delta $ in our results and the above $\mathrm{td}(H)\in O(\log \log n)$ bound are both best possible. We prove that $n$-vertex graphs of bounded treewidth are subgraphs of the product of a graph with tree-depth $t$ and a complete graph of size $O(n^{1/t})$, which is best possible. Finally, we investigate the conjecture that for any hereditary graph class $\mathcal{G}$ that admits $O(n^{1-\epsilon })$ separators, every $n$-vertex graph in $\mathcal{G}$ is a subgraph of the strong product of a graph $H$ with bounded tree-width and a complete graph of size $O(n^{1-\epsilon })$. We prove this for various classes $\mathcal{G}$ of interest.

Received:
Accepted:
Published online:
DOI: 10.5802/igt.10
Classification: 05C10, 05C83
Keywords: separators, treewidth, product structure

Dvořák, Zdeněk 1; Wood, David R. 2

1 Institute of Computer Science Charles University Prague, Czech Republic
2 School of Mathematics Monash University Melbourne, Australia
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{IGT_2025__2__191_0,
     author = {Dvo\v{r}\'ak, Zden\v{e}k and Wood, David R.},
     title = {Product {Structure} of {Graph} {Classes} with {Strongly} {Sublinear} {Separators}},
     journal = {Innovations in Graph Theory},
     pages = {191--222},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {2},
     year = {2025},
     doi = {10.5802/igt.10},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.10/}
}
TY  - JOUR
AU  - Dvořák, Zdeněk
AU  - Wood, David R.
TI  - Product Structure of Graph Classes with Strongly Sublinear Separators
JO  - Innovations in Graph Theory
PY  - 2025
SP  - 191
EP  - 222
VL  - 2
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.10/
DO  - 10.5802/igt.10
LA  - en
ID  - IGT_2025__2__191_0
ER  - 
%0 Journal Article
%A Dvořák, Zdeněk
%A Wood, David R.
%T Product Structure of Graph Classes with Strongly Sublinear Separators
%J Innovations in Graph Theory
%D 2025
%P 191-222
%V 2
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.10/
%R 10.5802/igt.10
%G en
%F IGT_2025__2__191_0
Dvořák, Zdeněk; Wood, David R. Product Structure of Graph Classes with Strongly Sublinear Separators. Innovations in Graph Theory, Volume 2 (2025), pp. 191-222. doi : 10.5802/igt.10. https://igt.centre-mersenne.org/articles/10.5802/igt.10/

[1] Alon, Noga; Ding, Guoli; Oporowski, Bogdan; Vertigan, Dirk Partitioning into graphs with only small components, J. Comb. Theory, Ser. B, Volume 87 (2003) no. 2, pp. 231-243 | DOI | MR | Zbl

[2] Alon, Noga; Seymour, Paul; Thomas, Robin A separator theorem for nonplanar graphs, J. Am. Math. Soc., Volume 3 (1990) no. 4, pp. 801-808 | DOI | MR | Zbl

[3] Aprile, Manuel; Fiorini, Samuel; Huynh, Tony; Joret, Gwenaël; Wood, David R. Smaller Extended Formulations for Spanning Tree Polytopes in Minor-closed Classes and Beyond, Electron. J. Comb., Volume 28 (2021) no. 4, Paper no. P4.47, 16 pages | DOI | MR | Zbl

[4] Bae, Sang Won; Baffier, Jean-François; Chun, Jinhee; Eades, Peter; Eickmeyer, Kord; Grilli, Luca; Hong, Seok-Hee; Korman, Matias; Montecchiani, Fabrizio; Rutter, Ignaz; Tóth, Csaba D. Gap-planar graphs, Theor. Comput. Sci., Volume 745 (2018), pp. 36-52 | DOI | MR | Zbl

[5] Barát, János; Wood, David R. Notes on nonrepetitive graph colouring, Electron. J. Comb., Volume 15 (2008), Paper no. R99, 13 pages | DOI | MR | Zbl

[6] Bekos, Michael A.; Grilli, Luca Fan-Planar Graphs, Beyond Planar Graphs (Hong, Seok-Hee; Tokuyama, Takeshi, eds.), Springer, 2020, pp. 131-148 | DOI | Zbl

[7] Bekos, Michael A.; Lozzo, Giordano Da; Hlinený, Petr; Kaufmann, Michael Graph Product Structure for h-Framed Graphs, Electron. J. Comb., Volume 31 (2024) no. 4, Paper no. P4.56, 33 pages | DOI | Zbl

[8] Bodlaender, Hans L. The complexity of finding uniform emulations on fixed graphs, Inf. Process. Lett., Volume 29 (1988) no. 3, pp. 137-141 | DOI | Zbl

[9] Bodlaender, Hans L. The complexity of finding uniform emulations on paths and ring networks, Inform. Comput., Volume 86 (1990) no. 1, pp. 87-106 | DOI | Zbl

[10] Bodlaender, Hans L. A partial k-arboretum of graphs with bounded treewidth, Theor. Comput. Sci., Volume 209 (1998) no. 1-2, pp. 1-45 | DOI | MR | Zbl

[11] Bodlaender, Hans L. A note on domino treewidth, Discrete Math. Theor. Comput. Sci., Volume 3 (1999) no. 4, pp. 141-150 https://dmtcs.episciences.org/256 | MR | Zbl

[12] Bodlaender, Hans L.; Engelfriet, Joost Domino treewidth, J. Algorithms, Volume 24 (1997) no. 1, pp. 94-123 | DOI | MR | Zbl

[13] Bodlaender, Hans L.; Groenland, Carla; Jacob, Hugo On the Parameterized Complexity of Computing Tree-Partitions, Proc. 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) (Dell, Holger; Nederlof, Jesper, eds.) (LIPIcs), Volume 249, Schloss Dagstuhl (2022), Paper no. 7, 20 pages | DOI | MR | Zbl

[14] Bodlaender, Hans L.; van Leeuwen, Jan Simulation of large networks on smaller networks, Inf. Control, Volume 71 (1986) no. 3, pp. 143-180 | DOI | Zbl

[15] Bollobás, Béla; Leader, Imre Edge-isoperimetric inequalities in the grid, Combinatorica, Volume 11 (1991) no. 4, pp. 299-314 | DOI | MR | Zbl

[16] Bonnet, Édouard; Kwon, O-joung; Wood, David R. Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond) (2022) | arXiv | DOI

[17] Bose, Prosenjit; Dujmović, Vida; Javarsineh, Mehrnoosh; Morin, Pat Asymptotically optimal vertex ranking of planar graphs (2020) | arXiv | DOI | Zbl

[18] Campbell, Rutger; Clinch, Katie; Distel, Marc; Gollin, J. Pascal; Hendrey, Kevin; Hickingbotham, Robert; Huynh, Tony; Illingworth, Freddie; Tamitegama, Youri; Tan, Jane; Wood, David R. Product structure of graph classes with bounded treewidth, Comb. Probab. Comput., Volume 33 (2024) no. 3, pp. 351-376 | DOI | MR | Zbl

[19] Carmi, Paz; Dujmović, Vida; Morin, Pat; Wood, David R. Distinct Distances in Graph Drawings, Electron. J. Comb., Volume 15 (2008), Paper no. R107, 23 pages https://www.combinatorics.org/v15i1r107 | MR | Zbl

[20] Chatzidimitriou, Dimitris; Raymond, Jean-Florent; Sau, Ignasi; Thilikos, Dimitrios M. An O(log OPT)-Approximation for Covering and Packing Minor Models of θ r , Algorithmica, Volume 80 (2018) no. 4, pp. 1330-1356 | DOI | MR | Zbl

[21] Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix Improved bounds for centered colorings, Adv. Comb. (2021), Paper no. 8, 28 pages | DOI | MR | Zbl

[22] Di Giacomo, Emilio; Liotta, Giuseppe; Meijer, Henk Computing Straight-line 3D Grid Drawings of Graphs in Linear Volume, Comput. Geom. Theory Appl., Volume 32 (2005) no. 1, pp. 26-58 | DOI | MR | Zbl

[23] Diestel, Reinhard Graph theory, Graduate Texts in Mathematics, 173, Springer, 2018

[24] Diestel, Reinhard; Kühn, Daniela Graph minor hierarchies, Discrete Appl. Math., Volume 145 (2005) no. 2, pp. 167-182 | DOI | MR | Zbl

[25] Ding, Guoli; Oporowski, Bogdan Some results on tree decomposition of graphs, J. Graph Theory, Volume 20 (1995) no. 4, pp. 481-499 | DOI | MR | Zbl

[26] Ding, Guoli; Oporowski, Bogdan On tree-partitions of graphs, Discrete Math., Volume 149 (1996) no. 1–3, pp. 45-58 | DOI | MR | Zbl

[27] Ding, Guoli; Oporowski, Bogdan; Sanders, Daniel P.; Vertigan, Dirk Partitioning graphs of bounded tree-width, Combinatorica, Volume 18 (1998) no. 1, pp. 1-12 | DOI | MR | Zbl

[28] Ding, Guoli; Oporowski, Bogdan; Sanders, Daniel P.; Vertigan, Dirk Surfaces, tree-width, clique-minors, and partitions, J. Comb. Theory, Ser. B, Volume 79 (2000) no. 2, pp. 221-246 | DOI | MR | Zbl

[29] Distel, Marc; Dujmović, Vida; Eppstein, David; Hickingbotham, Robert; Joret, Gwenaël; Micek, Piotr; Morin, Pat; Seweryn, Michał T.; Wood, David R. Product structure extension of the Alon–Seymour–Thomas Theorem, SIAM J. Discrete Math., Volume 38 (2024) no. 3, pp. 2095-2107 | DOI | Zbl

[30] Distel, Marc; Hickingbotham, Robert; Huynh, Tony; Wood, David R. Improved Product Structure for Graphs on Surfaces, Discrete Math. Theor. Comput. Sci., Volume 24 (2022) no. 2, Paper no. 6, Paper no. #6, 10 pages | DOI | MR | Zbl

[31] Distel, Marc; Hickingbotham, Robert; Seweryn, Michał T.; Wood, David R. Powers of planar graphs, product structure, and blocking partitions, Innov. Graph Theory, Volume 1 (2024), pp. 39-86 | DOI | MR | Zbl

[32] Distel, Marc; Wood, David R. Tree-Partitions with Bounded Degree Trees, 2021–2022 MATRIX Annals (Wood, David R.; de Gier, Jan; Praeger, Cheryl E., eds.), Springer, 2024, pp. 203-212 | DOI | Zbl

[33] Djidjev, Hristo N. A separator theorem, C. R. Acad. Bulg. Sci., Volume 34 (1981) no. 5, pp. 643-645 | MR | Zbl

[34] Draganić, Nemanja; Kaufmann, Marc; Correia, David Munhá; Petrova, Kalina; Steiner, Raphael Size-Ramsey numbers of structurally sparse graphs (2023) | arXiv | DOI | Zbl

[35] Dujmović, Vida; Eppstein, David; Wood, David R. Structure of Graphs with Locally Restricted Crossings, SIAM J. Discrete Math., Volume 31 (2017) no. 2, pp. 805-824 | DOI | MR | Zbl

[36] Dujmović, Vida; Esperet, Louis; Gavoille, Cyril; Joret, Gwenaël; Micek, Piotr; Morin, Pat Adjacency Labelling for Planar Graphs (and Beyond), J. ACM, Volume 68 (2021) no. 6, Paper no. 42, Paper no. #42, 33 pages | DOI | MR | Zbl

[37] Dujmović, Vida; Esperet, Louis; Joret, Gwenaël; Walczak, Bartosz; Wood, David R. Planar Graphs have Bounded Nonrepetitive Chromatic Number, Adv. Comb. (2020), Paper no. 5, 11 pages | DOI | MR | Zbl

[38] Dujmović, Vida; Joret, Gwenaël; Micek, Piotr; Morin, Pat; Ueckerdt, Torsten; Wood, David R. Planar Graphs have Bounded Queue-Number, J. ACM, Volume 67 (2020) no. 4, Paper no. 22, Paper no. #22, 38 pages | DOI | MR | Zbl

[39] Dujmović, Vida; Morin, Pat; Wood, David R. Layout of Graphs with Bounded Tree-Width, SIAM J. Comput., Volume 34 (2005) no. 3, pp. 553-579 | DOI | MR | Zbl

[40] Dujmović, Vida; Morin, Pat; Wood, David R. Layered Separators in Minor-Closed Graph Classes with Applications, J. Comb. Theory, Ser. B, Volume 127 (2017), pp. 111-147 | DOI | MR | Zbl

[41] Dujmović, Vida; Morin, Pat; Wood, David R. Graph product structure for non-minor-closed classes, J. Comb. Theory, Ser. B, Volume 162 (2023), pp. 34-67 | DOI | MR | Zbl

[42] Dujmović, Vida; Suderman, Matthew; Wood, David R. Graph Drawings with Few Slopes, Comput. Geom. Theory Appl., Volume 38 (2007), pp. 181-193 | DOI | MR | Zbl

[43] Dvořák, Zdeněk On weighted sublinear separators, J. Graph Theory, Volume 100 (2022) no. 2, pp. 270-280 | DOI | MR | Zbl

[44] Dvořák, Zdeněk; Gonçalves, Daniel; Lahiri, Abhiruk; Tan, Jane; Ueckerdt, Torsten On Comparable Box Dimension, Proc. 38th Int’l Symp. on Computat. Geometry (SoCG 2022) (Goaoc, Xavier; Kerber, Michael, eds.) (LIPIcs), Volume 224, Schloss Dagstuhl (2022), Paper no. 38, 14 pages | DOI | MR | Zbl

[45] Dvořák, Zdeněk; McCarty, Rose; Norin, Sergey Sublinear separators in intersection graphs of convex shapes, SIAM J. Discrete Math., Volume 35 (2021) no. 2, pp. 1149-1164 | DOI | MR | Zbl

[46] Dvořák, Zdeněk; Norin, Sergey Islands in minor-closed classes. I. Bounded treewidth and separators (2017) | arXiv | DOI | Zbl

[47] Dvořák, Zdeněk; Norin, Sergey Treewidth of graphs with balanced separations, J. Comb. Theory, Ser. B, Volume 137 (2019), pp. 137-144 | DOI | MR | Zbl

[48] Edenbrandt, Anders Quotient tree partitioning of undirected graphs, BIT, Volume 26 (1986) no. 2, pp. 148-155 | DOI | MR | Zbl

[49] Edwards, Keith; McDiarmid, Colin New upper bounds on harmonious colorings, J. Graph Theory, Volume 18 (1994) no. 3, pp. 257-267 | DOI | MR | Zbl

[50] Eppstein, David; Gupta, Siddharth Crossing Patterns in Nonplanar Road Networks, Proc. 25th ACM SIGSPATIAL Int’l Conf. on Advances in Geographic Information Systems (2017), Paper no. 40, 9 pages | DOI

[51] Esperet, Louis; Joret, Gwenaël; Morin, Pat Sparse Universal Graphs for Planarity, J. Lond. Math. Soc., Volume 108 (2023) no. 4, pp. 1333-1357 | DOI | MR | Zbl

[52] Fishburn, John P.; Finkel, Raphael A. Quotient Networks, IEEE Trans. Comput., Volume C-31 (1982) no. 4, pp. 288-295 | DOI | Zbl

[53] Giannopoulou, Archontia C.; Kwon, O-joung; Raymond, Jean-Florent; Thilikos, Dimitrios M. Packing and Covering Immersion Models of Planar Subcubic Graphs, Proc. 42nd Int’l Workshop on Graph-Theoretic Concepts in Computer Science (WG 2016) (Heggernes, Pinar, ed.) (Lecture Notes in Computer Science), Volume 9941, Springer (2016), pp. 74-84 | DOI | MR | Zbl

[54] Gilbert, John R.; Hutchinson, Joan P.; Tarjan, Robert E. A separator theorem for graphs of bounded genus, J. Algorithms, Volume 5 (1984) no. 3, pp. 391-407 | DOI | MR | Zbl

[55] Grigoriev, Alexander; Bodlaender, Hans L. Algorithms for Graphs Embeddable with Few Crossings per Edge, Algorithmica, Volume 49 (2007) no. 1, pp. 1-11 | DOI | MR | Zbl

[56] Halin, Rudolf Tree-partitions of infinite graphs, Discrete Math., Volume 97 (1991), pp. 203-217 | DOI | MR | Zbl

[57] Hickingbotham, Robert; Wood, David R. Shallow Minors, Graph Products and Beyond-Planar Graphs, SIAM J. Discrete Math., Volume 38 (2024) no. 1, pp. 1057-1089 | DOI | MR | Zbl

[58] Illingworth, Freddie; Scott, Alex; Wood, David R. Product structure of graphs with an excluded minor, Trans. Amer. Math. Soc., Ser. B, Volume 11 (2024), pp. 1233-1248 | DOI | MR | Zbl

[59] Jacob, Hugo; Pilipczuk, Marcin Bounding Twin-Width for Bounded-Treewidth Graphs, Planar Graphs, and Bipartite Graphs, Proc. 48th Int’l Workshop on Graph-Theoretic Concepts in Comput. Sci. (WG 2022) (Bekos, Michael A.; Kaufmann, Michael, eds.) (Lecture Notes in Computer Science), Volume 13453, Springer (2022), pp. 287-299 | DOI | MR | Zbl

[60] Kaufmann, Michael; Ueckerdt, Torsten The Density of Fan-Planar Graphs, Electron. J. Comb., Volume 29 (2022) no. 1, Paper no. P1.29, 25 pages | DOI | MR | Zbl

[61] Kráľ, Daniel; Pekárková, Kristýna; Štorgel, Kenny Twin-Width of Graphs on Surfaces, Proc. 49th Int’l Symp. on Math’l Foundations of Comput. Sci. (MFCS 2024) (Královič, Rastislav; Kučera, Antonín, eds.) (LIPIcs), Volume 306, Schloss Dagstuhl (2024), Paper no. 66, 15 pages https://drops.dagstuhl.de/... | DOI | MR

[62] Kuske, Dietrich; Lohrey, Markus Logical aspects of Cayley-graphs: the group case, Ann. Pure Appl. Logic, Volume 131 (2005) no. 1–3, pp. 263-286 | DOI | MR | Zbl

[63] Lee, James R. Separators in region intersection graphs (2016) | arXiv | DOI

[64] Lee, James R. Separators in region intersection graphs, Proc. 8th Innovations in Theoretical Computer Science Conference (Papadimitriou, Christos H., ed.) (LIPIcs), Volume 67, Schloss Dagstuhl, 2017, Paper no. 1, 8 pages | DOI | Zbl

[65] Linial, Nathan; Matoušek, Jiří; Sheffet, Or; Tardos, Gábor Graph colouring with no large monochromatic components, Comb. Probab. Comput., Volume 17 (2008) no. 4, pp. 577-589 | DOI | MR | Zbl

[66] Lipton, Richard J.; Tarjan, Robert E. A separator theorem for planar graphs, SIAM J. Appl. Math., Volume 36 (1979) no. 2, pp. 177-189 | DOI | MR | Zbl

[67] Lipton, Richard J.; Tarjan, Robert E. Applications of a planar separator theorem, SIAM J. Comput., Volume 9 (1980) no. 3, pp. 615-627 | DOI | MR

[68] Ossona de Mendez, Patrice; Oum, Sang-il; Wood, David R. Defective colouring of graphs excluding a subgraph or minor, Combinatorica, Volume 39 (2019) no. 2, pp. 377-410 | DOI | MR | Zbl

[69] Miller, Gary L.; Teng, Shang-Hua; Thurston, William; Vavasis, Stephen A. Separators for sphere-packings and nearest neighbor graphs, J. ACM, Volume 44 (1997) no. 1, pp. 1-29 | DOI | MR | Zbl

[70] Mohar, Bojan; Thomassen, Carsten Graphs on surfaces, Johns Hopkins University Press, 2001 | DOI | MR | Zbl

[71] Nešetřil, Jaroslav; Ossona de Mendez, Patrice Sparsity, Algorithms and Combinatorics, 28, Springer, 2012 | DOI | MR | Zbl

[72] Raymond, Jean-Florent; Thilikos, Dimitrios M. Recent techniques and results on the Erdős–Pósa property, Discrete Appl. Math., Volume 231 (2017), pp. 25-43 | DOI | MR | Zbl

[73] Reed, Bruce A.; Seymour, Paul Fractional colouring and Hadwiger’s conjecture, J. Comb. Theory, Ser. B, Volume 74 (1998) no. 2, pp. 147-152 | DOI | MR | Zbl

[74] Robertson, Neil; Seymour, Paul Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, Volume 7 (1986) no. 3, pp. 309-322 | DOI | MR | Zbl

[75] Robertson, Neil; Seymour, Paul Graph minors. V. Excluding a planar graph, J. Comb. Theory, Ser. B, Volume 41 (1986) no. 1, pp. 92-114 | DOI | MR | Zbl

[76] Seese, Detlef Tree-partite graphs and the complexity of algorithms, Proc. Int’l Conf. on Fundamentals of Computation Theory (Budach, Lothar, ed.) (Lecture Notes in Computer Science), Volume 199, Springer (1985), pp. 412-421 | DOI | Zbl

[77] Smith, Warren D.; Wormald, Nicholas C. Geometric Separator Theorems & Applications, Proc. 39th Annual Symp. on Foundations of Comput. Sci. (FOCS ’98), IEEE (1998), pp. 232-243 | DOI

[78] Thomassen, Carsten On the presence of disjoint subgraphs of a specified type, J. Graph Theory, Volume 12 (1988) no. 1, pp. 101-111 | DOI | MR | Zbl

[79] Ueckerdt, Torsten; Wood, David R.; Yi, Wendy An improved planar graph product structure theorem, Electron. J. Comb., Volume 29 (2022), Paper no. P2.51, 12 pages | DOI | MR | Zbl

[80] Wood, David R. Vertex partitions of chordal graphs, J. Graph Theory, Volume 53 (2006) no. 2, pp. 167-172 | DOI | MR | Zbl

[81] Wood, David R. On tree-partition-width, Eur. J. Comb., Volume 30 (2009) no. 5, pp. 1245-1253 | DOI | MR | Zbl

[82] Wood, David R. Defective and Clustered Graph Colouring, Electron. J. Comb., Volume DS23 (2018) (Version 1) | DOI | MR | Zbl

[83] Wood, David R.; Telle, Jan Arne Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor, New York J. Math., Volume 13 (2007), pp. 117-146 http://nyjm.albany.edu/j/2007/13-8.html | MR | Zbl

[84] Zhang, Rui-Ray; Amini, Massih-Reza Generalization bounds for learning under graph-dependence: a survey, Mach. Learn., Volume 113 (2024) no. 7, pp. 3929-3959 | DOI | MR

Cited by Sources: