Powers of planar graphs, product structure, and blocking partitions

EUROCOMB’23

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

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-049

PDF
Abstract
We show that there exist a constant \(c\) and a function \(f\) such that the \(k\)-power of a planar graph with maximum degree \(\Delta\) is isomorphic to a subgraph of \(H \boxtimes P \boxtimes K_{f(\Delta, k)}\) for some graph \(H\) with treewidth at most \(c\) and some path \(P\). This is the first product structure theorem for \(k\)-powers of planar graphs, where the treewidth of \(H\) does not depend on \(k\). We actually prove a stronger result, which implies an analogous product structure theorem for other graph classes, including \(k\)-planar graphs (of arbitrary degree). Our proof uses a new concept of blocking partitions which is of independent interest. An \(\ell\)-blocking partition of a graph \(G\) is a partition of the vertex set of \(G\) into connected subsets such that every path in \(G\) of length greater than \(\ell\) contains two vertices in one set of the partition. The key lemma in our proof states that there exists a positive integer \(\ell\) such that every planar graph of maximum degree \(\Delta\) has an \(\ell\)-blocking partition with parts of size bounded in terms of \(\Delta\).

Pages:
355–361
References

Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný, and Michael Kaufmann. Graph product structure for h-framed graphs. In Sang Won Bae and Heejin Park, editors, 33rd International Symposium on Algorithms and Computation (ISAAC '22), volume 248 of LIPIcs, pages 23:1-23. Schloss Dagstuhl, 2022.

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

Marc Distel, Robert Hickingbotham, Tony Huynh, and David R. Wood. Improved product structure for graphs on surfaces. Discrete Math. Theor. Comput. Sci., 24(2):#6, 2022.
https://doi.org/10.46298/dmtcs.8877

Michał Dębski, Stefan Felsner, Piotr Micek, and Felix Schröder. Improved bounds for centered colorings. Adv. Comb., #8, 2021.
https://doi.org/10.19086/aic.27351

Vida Dujmović, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, and Pat Morin. Adjacency labelling for planar graphs (and beyond). J. ACM, 68(6):42, 2021.
https://doi.org/10.1145/3477542

Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, and David R. Wood. Planar graphs have bounded nonrepetitive chromatic number. Adv. Comb., #5, 2020.
https://doi.org/10.19086/aic.12100

Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood. Planar graphs have bounded queue-number. J. ACM, 67(4):#22, 2020.
https://doi.org/10.1145/3385731

Vida Dujmović, Pat Morin, and David R. Wood. Graph product structure for non-minor-closed classes, 2019.

Zdenek Dvorák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt. On comparable box dimension. In Xavier Goaoc and Michael Kerber, editors, Proc. 38th Int'l Symp. on Computat. Geometry (SoCG 2022), volume 224 of LIPIcs, pages 38:1-38:14. Schloss Dagstuhl, 2022.

Louis Esperet, Gwenaël Joret, and Pat Morin. Sparse universal graphs for planarity, 2020, arXiv:2010.05779.

Robert Hickingbotham and David R. Wood. Shallow minors, graph products and beyond planar graphs, 2021, arXiv:2111.12412.

Freddie Illingworth, Alex Scott, and David R. Wood. Product structure of graphs with an excluded minor, 2022, arXiv:2104.06627.

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

Torsten Ueckerdt, David R. Wood, and Wendy Yi. An improved planar graph product structure theorem. Electron. J. Combin., 29:P2.51, 2022.
https://doi.org/10.37236/10614

Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz, Roman Rabinovich, and Sebastian Siebertz. On the generalised colouring numbers of graphs that exclude a fixed minor. European J. Combin., 66:129-144, 2017.
https://doi.org/10.1016/j.ejc.2017.06.019

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Marc Distel, Robert Hickingbotham, Michał T. Seweryn, David R. Wood

PDF