We prove that the
At the heart of our proof is the following new concept of independent interest. An
Accepted:
Published online:
Keywords: graph, planar graph, product structure, power, blocking partition, surface, minor
Distel, Marc 1; Hickingbotham, Robert 2; Seweryn, Michał T. 3; Wood, David R. 1

@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/
[1] 1-fan-bundle-planar drawings of graphs, Theor. Comput. Sci., Volume 723 (2018), pp. 23-50 | DOI | MR
[2] Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond) (2022) | arXiv
[3] Asymptotically optimal vertex ranking of planar graphs (2020) | arXiv
[4] Product structure of graph classes with bounded treewidth, Comb. Probab. Comput., Volume 33 (2024) no. 3, pp. 351-376 | DOI | MR | Zbl
[5] Improved bounds for centered colorings, Adv. Comb., Volume 2021 (2021), Paper no. 8, 28 pages | DOI | MR | Zbl
[6] A Survey on Graph Drawing Beyond Planarity, ACM Comput. Surv., Volume 52 (2019) no. 1, p. 4:1-4:37 | DOI
[7] Graph theory, Graduate Texts in Mathematics, 173, Springer, 2018 | MR
[8] Some results on tree decomposition of graphs, J. Graph Theory, Volume 20 (1995) no. 4, pp. 481-499 | DOI | MR | Zbl
[9] Improved Product Structure for Graphs on Surfaces, Discrete Math. Theor. Comput. Sci., Volume 24 (2022) no. 2, Paper no. 6, 10 pages | MR | Zbl
[10] 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] Structure of Graphs with Locally Restricted Crossings, SIAM J. Discrete Math., Volume 31 (2017) no. 2, pp. 805-824 | DOI | MR | Zbl
[12] Adjacency Labelling for Planar Graphs (and Beyond), J. ACM, Volume 68 (2021) no. 6, Paper no. 42, 33 pages | DOI | MR | Zbl
[13] Planar Graphs have Bounded Nonrepetitive Chromatic Number, Adv. Comb., Volume 2020 (2020), Paper no. 5, 11 pages | DOI | MR | Zbl
[14] The Grid-Minor Theorem revisited, Proc. 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’24) (2023), pp. 1241-1245 | DOI | MR
[15] The Excluded Tree Minor Theorem Revisited, Comb. Probab. Comput., Volume 33 (2024) no. 1, pp. 85-90 | DOI | MR | Zbl
[16] Planar Graphs have Bounded Queue-Number, J. ACM, Volume 67 (2020) no. 4, Paper no. 22, 38 pages | DOI | MR | Zbl
[17] Layered Separators in Minor-Closed Graph Classes with Applications, J. Comb. Theory, Ser. B, Volume 127 (2017), pp. 111-147 | DOI | MR | Zbl
[18] Graph product structure for non-minor-closed classes, J. Comb. Theory, Ser. B, Volume 162 (2023), pp. 34-67 | DOI | MR | Zbl
[19] 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 | MR | Zbl
[20] Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, Volume 12 (1963), pp. 251-257 | MR | Zbl
[21] Sparse Universal Graphs for Planarity, J. Lond. Math. Soc., Volume 108 (2023) no. 4, pp. 1333-1357 | DOI | MR | Zbl
[22] A separator theorem for string graphs and its applications, Comb. Probab. Comput., Volume 19 (2010) no. 3, pp. 371-390 | DOI | MR | Zbl
[23] String graphs and incomparability graphs, Adv. Math., Volume 230 (2012) no. 3, pp. 1381-1401 | DOI | MR
[24] Algorithms for Graphs Embeddable with Few Crossings per Edge, Algorithmica, Volume 49 (2007) no. 1, pp. 1-11 | DOI | MR | Zbl
[25] On the Generalised Colouring Numbers of Graphs that Exclude a Fixed Minor, Eur. J. Comb., Volume 66 (2017), pp. 129-144 | DOI | MR | Zbl
[26] Shallow Minors, Graph Products and Beyond-Planar Graphs, SIAM J. Discrete Math., Volume 38 (2024) no. 1, pp. 1057-1089 | DOI | MR | Zbl
[27] Beyond Planar Graphs (Hong, Seok-Hee; Tokuyama, Takeshi, eds.), Springer, 2020 | DOI
[28] Product structure of graphs with an excluded minor, Trans. Amer. Math. Soc., Ser. B, Volume 11 (2024), pp. 1233-1248 | DOI | MR
[29] 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
[30] 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 | MR
[31] Near-optimal separators in string graphs, Comb. Probab. Comput., Volume 23 (2014) no. 1, pp. 135-139 | DOI | MR | Zbl
[32] Product structure for squares of planar graphs, 2021 Open Problems for Workshop on Graph Product Structure Theory, Banff International Research Station (21w5235)
[33] Graphs on surfaces, Johns Hopkins University Press, 2001 | MR
[34] Grad and classes with bounded expansion I. Decompositions, Eur. J. Comb., Volume 29 (2008) no. 3, pp. 760-776 | DOI | Zbl
[35] Graphs drawn with few crossings per edge, Combinatorica, Volume 17 (1997) no. 3, pp. 427-439 | DOI | MR | Zbl
[36] Recognizing string graphs is decidable, Discrete Comput. Geom., Volume 28 (2002) no. 4, pp. 593-606 | DOI | MR
[37] Polynomial bounds for centered colorings on proper minor-closed graph classes, J. Comb. Theory, Ser. B, Volume 151 (2021), pp. 111-147 | DOI | MR | Zbl
[38] Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, Volume 7 (1986) no. 3, pp. 309-322 | DOI | MR | Zbl
[39] Decidability of string graphs, J. Comput. Syst. Sci., Volume 68 (2004) no. 2, pp. 319-334 | DOI | MR | Zbl
[40] On tree-partition-width, Eur. J. Comb., Volume 30 (2009) no. 5, pp. 1245-1253 | DOI | MR | Zbl
- Product Structure and Tree-Decompositions, arXiv (2024) | DOI:10.48550/arxiv.2410.20333 | arXiv:2410.20333
- Grid Minors and Products, arXiv (2024) | DOI:10.48550/arxiv.2402.14181 | arXiv:2402.14181
- Planar graphs in blowups of fans, arXiv (2024) | DOI:10.48550/arxiv.2407.05936 | arXiv:2407.05936
- Product structure of graph classes with strongly sublinear separators, arXiv (2022) | DOI:10.48550/arxiv.2208.10074 | arXiv:2208.10074
Cited by 4 documents. Sources: NASA ADS