Powers of planar graphs, product structure, and blocking partitions

Distel, Marc; Hickingbotham, Robert; Seweryn, Michał T.; Wood, David R.

doi:10.5802/igt.4

Distel, Marc ¹; Hickingbotham, Robert ²; Seweryn, Michał T.³; Wood, David R.¹

¹ School of Mathematics Monash University Melbourne, Australia
² Laboratoire de l’Informatique du Parallélisme École Normale Supérieure de Lyon Lyon, France
³ Computer Science Institute Charles University Prague, Czech Republic

Innovations in Graph Theory, Volume 1 (2024), pp. 39-86.

Abstract

We prove that the $k$ -power of any planar graph $G$ is contained in $H ⊠ P ⊠ K_{f (Δ (G), k)}$ for some graph $H$ with bounded treewidth, some path $P$ , and some function $f$ . This resolves an open problem of Ossona de Mendez. In fact, we prove a more general result in terms of shallow minors that implies similar results for many ‘beyond planar’ graph classes, without dependence on $Δ (G)$ . For example, we prove that every $k$ -planar graph is contained in $H ⊠ P ⊠ K_{f (k)}$ for some graph $H$ with bounded treewidth and some path $P$ , and some function $f$ . This resolves an open problem of Dujmović, Morin and Wood. We generalise all these results for graphs of bounded Euler genus, still with an absolute bound on the treewidth.

At the heart of our proof is the following new concept of independent interest. An $ℓ$ -blocking partition of a graph $G$ is a partition of $V (G)$ into connected sets such that every path of length greater than $ℓ$ in $G$ contains at least two vertices in one part. We prove that for some constant $ℓ \geq 1$ every graph of Euler genus $g$ has an $ℓ$ -blocking partition with parts of size bounded by a function of $Δ (G)$ and $g$ . Motivated by this result, we study blocking partitions in their own right. We show that every graph $G$ has a $2$ -blocking partition with parts of size bounded by a function of $Δ (G)$ and $tw (G)$ . On the other hand, we show that 4-regular graphs do not have $ℓ$ -blocking partitions with bounded size parts.

Received: 2023-09-21
Accepted: 2024-09-03
Published online: 2024-11-26

DOI: 10.5802/igt.4

Classification: 05C10
Mots-clés : graph, planar graph, product structure, power, blocking partition, surface, minor

Author's affiliations:

Distel, Marc ¹; Hickingbotham, Robert ²; Seweryn, Michał T. ³; Wood, David R. ¹

¹ School of Mathematics Monash University Melbourne, Australia
² Laboratoire de l’Informatique du Parallélisme École Normale Supérieure de Lyon Lyon, France
³ Computer Science Institute Charles University Prague, Czech Republic

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{IGT_2024__1__39_0,
     author = {Distel, Marc and Hickingbotham, Robert and Seweryn, Micha{\l} T. and Wood, David R.},
     title = {Powers of planar graphs, product structure, and blocking partitions},
     journal = {Innovations in Graph Theory},
     pages = {39--86},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {1},
     year = {2024},
     doi = {10.5802/igt.4},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.4/}
}

TY  - JOUR
AU  - Distel, Marc
AU  - Hickingbotham, Robert
AU  - Seweryn, Michał T.
AU  - Wood, David R.
TI  - Powers of planar graphs, product structure, and blocking partitions
JO  - Innovations in Graph Theory
PY  - 2024
SP  - 39
EP  - 86
VL  - 1
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.4/
DO  - 10.5802/igt.4
LA  - en
ID  - IGT_2024__1__39_0
ER  -

%0 Journal Article
%A Distel, Marc
%A Hickingbotham, Robert
%A Seweryn, Michał T.
%A Wood, David R.
%T Powers of planar graphs, product structure, and blocking partitions
%J Innovations in Graph Theory
%D 2024
%P 39-86
%V 1
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.4/
%R 10.5802/igt.4
%G en
%F IGT_2024__1__39_0

Distel, Marc; Hickingbotham, Robert; Seweryn, Michał T.; Wood, David R. Powers of planar graphs, product structure, and blocking partitions. Innovations in Graph Theory, Volume 1 (2024), pp. 39-86. doi : 10.5802/igt.4. https://igt.centre-mersenne.org/articles/10.5802/igt.4/

References
Cited by

[1] Angelini, Patrizio; Bekos, Michael A.; Kaufmann, Michael; Kindermann, Philipp; Schneck, Thomas 1-fan-bundle-planar drawings of graphs, Theor. Comput. Sci., Volume 723 (2018), pp. 23-50 | DOI

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

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

[4] 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 | Zbl

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

[6] Didimo, Walter; Liotta, Giuseppe; Montecchiani, Fabrizio A Survey on Graph Drawing Beyond Planarity, ACM Comput. Surv., Volume 52 (2019) no. 1, p. 4:1-4:37 | DOI

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

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

[9] 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, 10 pages | Zbl

[10] 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

[11] 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 | Zbl

[12] 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, 33 pages | DOI | Zbl

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

[14] Dujmović, Vida; Hickingbotham, Robert; Hodor, Jędrzej; Joret, Gwenaël; La, Hoang; Micek, Piotr; Morin, Pat; Rambaud, Clément; Wood, David R. The Grid-Minor Theorem revisited, Proc. 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’24) (2023), pp. 1241-1245 | DOI

[15] Dujmović, Vida; Hickingbotham, Robert; Joret, Gwenaël; Micek, Piotr; Morin, Pat; Wood, David R. The Excluded Tree Minor Theorem Revisited, Comb. Probab. Comput., Volume 33 (2024) no. 1, pp. 85-90 | DOI | Zbl

[16] 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, 38 pages | DOI | Zbl

[17] 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 | Zbl

[18] 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 | Zbl

[19] Dvorák, Zdenek; 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), p. 38:1-38:14 | DOI | Zbl

[20] Erdős, Paul; Sachs, Horst Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, Volume 12 (1963), pp. 251-257 | Zbl

[21] 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 | Zbl

[22] Fox, Jacob; Pach, János A separator theorem for string graphs and its applications, Comb. Probab. Comput., Volume 19 (2010) no. 3, pp. 371-390 | DOI | Zbl

[23] Fox, Jacob; Pach, János String graphs and incomparability graphs, Adv. Math., Volume 230 (2012) no. 3, pp. 1381-1401 | DOI

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

[25] van den Heuvel, Jan; Ossona de Mendez, Patrice; Quiroz, Daniel; Rabinovich, Roman; Siebertz, Sebastian On the Generalised Colouring Numbers of Graphs that Exclude a Fixed Minor, Eur. J. Comb., Volume 66 (2017), pp. 129-144 | DOI | Zbl

[26] 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 | Zbl

[27] Beyond Planar Graphs (Hong, Seok-Hee; Tokuyama, Takeshi, eds.), Springer, 2020 | DOI

[28] 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

[29] 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 | Zbl

[30] 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), p. 66:1-66:15 | DOI

[31] Matoušek, Jiří Near-optimal separators in string graphs, Comb. Probab. Comput., Volume 23 (2014) no. 1, pp. 135-139 | DOI | Zbl

[32] Ossona de Mendez, Patrice Product structure for squares of planar graphs, 2021 Open Problems for Workshop on Graph Product Structure Theory, Banff International Research Station (21w5235)

[33] Mohar, Bojan; Thomassen, Carsten Graphs on surfaces, Johns Hopkins University Press, 2001

[34] Nešetřil, Jaroslav; Ossona de Mendez, Patrice Grad and classes with bounded expansion I. Decompositions, Eur. J. Comb., Volume 29 (2008) no. 3, pp. 760-776 | DOI | Zbl

[35] Pach, János; Tóth, Géza Graphs drawn with few crossings per edge, Combinatorica, Volume 17 (1997) no. 3, pp. 427-439 | DOI | Zbl

[36] Pach, János; Tóth, Géza Recognizing string graphs is decidable, Discrete Comput. Geom., Volume 28 (2002) no. 4, pp. 593-606 | DOI

[37] Pilipczuk, Michał; Siebertz, Sebastian Polynomial bounds for centered colorings on proper minor-closed graph classes, J. Comb. Theory, Ser. B, Volume 151 (2021), pp. 111-147 | DOI | Zbl

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

[39] Schaefer, Marcus; Štefankovič, Daniel Decidability of string graphs, J. Comput. Syst. Sci., Volume 68 (2004) no. 2, pp. 319-334 | DOI | Zbl

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

Cited by Sources:

BROWSE ISSUES

About the journal

Editorial Board

Submit a paper