More Web Proxy on the site http://driver.im/

research-article

Graph product structure for non-minor-closed classes

Authors:

Vida Dujmović,

David R. WoodAuthors Info & Claims

Volume 162, Issue C

Pages 34 - 67

https://doi.org/10.1016/j.jctb.2023.03.004

Published: 01 September 2023 Publication History

Abstract

Dujmović et al. [J. ACM '20] proved that every planar graph is isomorphic to a subgraph of the strong product of a bounded treewidth graph and a path. Analogous results were obtained for graphs of bounded Euler genus or apex-minor-free graphs. These tools have been used to solve longstanding problems on queue layouts, non-repetitive colouring, p-centered colouring, and adjacency labelling. This paper proves analogous product structure theorems for various non-minor-closed classes. One noteable example is k-planar graphs (those with a drawing in the plane in which each edge is involved in at most k crossings). We prove that every k-planar graph is isomorphic to a subgraph of the strong product of a graph of treewidth O ( k 5 ) and a path. This is the first result of this type for a non-minor-closed class of graphs. It implies, amongst other results, that k-planar graphs have non-repetitive chromatic number upper-bounded by a function of k. All these results generalise for drawings of graphs on arbitrary surfaces. In fact, we work in a more general setting based on so-called shortcut systems, which are of independent interest. This leads to analogous results for certain types of map graphs, string graphs, graph powers, and nearest neighbour graphs.

References

[1]

Bernardo M. Ábrego, Ruy Fabila Monroy, Silvia Fernández-Merchant, David Flores-Peñaloza, Ferran Hurtado, Vera Sacristán, Maria Saumell, On crossing numbers of geometric proximity graphs, Comput. Geom. 44 (4) (2011) 216–233.

[2]

Martin Aigner, Günter M. Ziegler, Proofs from the Book, 4th edn., Springer, 2010.

[3]

Miklós Ajtai, Vašek Chvátal, Monroe M. Newborn, Endre Szemerédi, Crossing-free subgraphs, Ann. Discrete Math. 12 (1982) 9–12.

[4]

Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann, Michael Kaufmann, Sergey Pupyrev, Queue layouts of planar 3-trees, Algorithmica 82 (2020) 2564–2585.

[5]

Noga Alon, Jarosław Grytczuk, Mariusz Hałuszczak, Oliver Riordan, Nonrepetitive colorings of graphs, Random Struct. Algorithms 21 (3–4) (2002) 336–346.

[6]

Laszlo Babai, F.R.K. Chung, Paul Erdős, Ronald L. Graham, J.H. Spencer, On graphs which contain all sparse graphs, in: Theory and Practice of Combinatorics. A Collection of Articles Honoring Anton Kotzig on the Occasion of His Sixtieth Birthday, Elsevier, 1982, pp. 21–26.

[7]

Michael A. Bekos, Giordano Da Lozzo, Svenja Griesbach, Martin Gronemann, Fabrizio Montecchiani, Chrysanthi N. Raftopoulou, Book embeddings of nonplanar graphs with small faces in few pages, in: Sergio Cabello, Danny Z. Chen (Eds.), 36th International Symposium on Computational Geometry, in: LIPIcs, vol. 164, SoCG 2020, June 23-26, 2020, Zürich, Switzerland, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, pp. 16:1–16:17. arXiv:2003.07655.

[8]

Hans L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theor. Comput. Sci. 209 (1–2) (1998) 1–45.

Digital Library

[9]

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

[10]

Prosenjit Bose, Vida Dujmovic Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Vera Sacristán Adinolfi, Maria Saumell, David R. Wood, Proximity graphs: E, δ, Δ, χ and ω, Int. J. Comput. Geom. Appl. 22 (5) (2012) 439–470.

[11]

Bose, Prosenjit; Dujmović, Vida; Javarsineh, Mehrnoosh; Morin, Pat (2020): Asymptotically optimal vertex ranking of planar graphs. arXiv:2007.06455.

[12]

Prosenjit Bose, Pat Morin, Saeed Odak, An optimal algorithm for product structure in planar graphs, in: Artur Czumaj, Qin Xin (Eds.), Proc. 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022), in: Leibniz International Proceedings in Informatics (LIPIcs), vol. 227, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, pp. 19:1–19:14.

[13]

Prosenjit Bose, Pat Morin, Ivan Stojmenović, Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Wirel. Netw. 7 (6) (2001) 609–616.

[14]

Franz J. Brandenburg, Characterizing and recognizing 4-map graphs, Algorithmica 81 (5) (2019) 1818–1843.

Digital Library

[15]

Brandenburg, Franz J. (2020): Book embeddings of k-map graphs. arXiv:2012.06874.

[16]

Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou, Map graphs, J. ACM 49 (2) (2002) 127–138.

[17]

Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou, Recognizing hole-free 4-map graphs in cubic time, Algorithmica 45 (2) (2006) 227–262.

Digital Library

[18]

Reinhard Diestel, Graph Theory, Graduate Texts in Mathematics, vol. 173, 5th edn., Springer, 2018.

[19]

Marc Distel, Robert Hickingbotham, Tony Huynh, David R. Wood, Improved product structure for graphs on surfaces, Discrete Math. Theor. Comput. Sci. 24 (2) (2022) 6.

[20]

Michał Dębski, Stefan Felsner, Piotr Micek, Felix Schröder, Improved bounds for centered colorings, Adv. Combust. 8 (2021).

[21]

Vida Dujmović, David Eppstein, David R. Wood, Structure of graphs with locally restricted crossings, SIAM J. Discrete Math. 31 (2) (2017) 805–824.

[22]

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

[23]

Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, David R. Wood, Planar graphs have bounded nonrepetitive chromatic number, Adv. Combust. 5 (2020).

[24]

Vida Dujmović, Louis Esperet, Pat Morin, Bartosz Walczak, David R. Wood, Clustered 3-colouring graphs of bounded degree, Comb. Probab. Comput. 31 (1) (2022) 123–135.

[25]

Vida Dujmović, Gwenaël Joret, Jakub Kozik, David R. Wood, Nonrepetitive colouring via entropy compression, Combinatorica 36 (6) (2016) 661–686.

[26]

Vida Dujmovic, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood, Planar graphs have bounded queue-number, J. ACM 67 (4) (2020) 22:1–22:38.

[27]

Vida Dujmović, Pat Morin, David R. Wood, Layered separators in minor-closed graph classes with applications, J. Comb. Theory, Ser. B 127 (2017) 111–147.

[28]

Zdeněk Dvořák, Tony Huynh, Gwenaël Joret, Chun-Hung Liu, David R. Wood, Notes on graph product structure theory, in: David R. Wood, Jan de Gier, Cheryl E. Praeger, Terence Tao (Eds.), 2019-20 MATRIX Annals, Springer, 2021, pp. 513–533. arXiv:2001.08860.

[29]

Ehab S. Elmallah, Charles J. Colbourn, On two dual classes of planar graphs, Discrete Math. 80 (1) (1990) 21–40.

[30]

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

[31]

Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Bidimensionality and geometric graphs, in: Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 2012, pp. 1563–1575.

[32]

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

[33]

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

[34]

Daniel J. Harvey, David R. Wood, Parameters tied to treewidth, J. Graph Theory 84 (4) (2017) 364–385.

[35]

Lenwood S. Heath, F. Thomson Leighton, Arnold L. Rosenberg, Comparing queues and stacks as mechanisms for laying out graphs, SIAM J. Discrete Math. 5 (3) (1992) 398–412.

Digital Library

[36]

Sampath Kannan, Moni Naor, Steven Rudich, Implicit representation of graphs, SIAM J. Discrete Math. 5 (4) (1992) 596–603.

Digital Library

[37]

Kolja Knauer, Torsten Ueckerdt, Simple treewidth, in: Pavel Rytír (Ed.), Midsummer Combinatorial Workshop Prague, 2012.

[38]

Stephen G. Kobourov, Giuseppe Liotta, Fabrizio Montecchiani, An annotated bibliography on 1-planarity, Comput. Sci. Rev. 25 (2017) 49–67.

[39]

Kratochvíl, Jan; Vaner, Michal (2012): A note on planar partial 3-trees. arXiv:1210.8113.

[40]

F. Thomson Leighton, Complexity Issues in VLSI, MIT Press, Cambridge, MA, 1983.

[41]

Bojan Mohar, Carsten Thomassen, Graphs on Surfaces, Johns Hopkins University Press, 2001.

[42]

Jaroslav Nešetřil, Patrice Ossona de Mendez Sparsity, Algorithms and Combinatorics, vol. 28, Springer, 2012.

[43]

János Pach, Géza Tóth, Recognizing string graphs is decidable, Discrete Comput. Geom. 28 (4) (2002) 593–606.

[44]

Michał Pilipczuk, Sebastian Siebertz, Polynomial bounds for centered colorings on proper minor-closed graph classes, J. Comb. Theory, Ser. B 151 (2021) 111–147.

[45]

Bruce A. Reed, Algorithmic Aspects of Tree Width, Recent Advances in Algorithms and Combinatorics, vol. 11, Springer, 2003, pp. 85–107.

[46]

Torsten Ueckerdt, David R. Wood, Wendy Yi, An improved planar graph product structure theorem, Electron. J. Comb. 29 (2022) 2.51.

[47]

Jan van den Heuvel, David R. Wood, Improper colourings inspired by Hadwiger's conjecture, J. Lond. Math. Soc. 98 (2018) 129–148. arXiv:1704.06536.

[48]

David R. Wood, Nonrepetitive graph colouring, Electron. J. Comb. DS24 (2021).

[49]

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

Cited By

Joret GRambaud C(2024)Neighborhood Complexity of Planar GraphsCombinatorica10.1007/s00493-024-00110-644:5(1115-1148)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s00493-024-00110-6

Recommendations

Planar Graphs Have Bounded Queue-Number

We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath et al. [66] from 1992. The key to the proof is a new structural tool called layered partitions, and the result that every planar graph has a vertex-partition and a ...
Strengthening Erdös–Pósa property for minor-closed graph classes

Let ℋ︁ and 𝒢 be graph classes. We say that ℋ︁ has the Erdős–Pósa property for 𝒢 if for any graph G ∈𝒢, the minimum vertex covering of all ℋ︁-subgraphs of G is bounded by a function f of the maximum packing of ℋ︁-subgraphs in G (by ℋ︁-subgraph of G we ...
Weak-Dynamic Coloring of Graphs Beyond-Planarity
Abstract
A weak-dynamic coloring of a graph is a vertex coloring (not necessarily proper) in such a way that each vertex of degree at least two sees at least two colors in its neighborhood. It is proved that the weak-dynamic chromatic number of the class ... $_{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Combinatorial Theory Series B

Journal of Combinatorial Theory Series B Volume 162, Issue C

Sep 2023

244 pages

ISSN:0095-8956

Issue’s Table of Contents

Elsevier Inc.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 September 2023

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Joret GRambaud C(2024)Neighborhood Complexity of Planar GraphsCombinatorica10.1007/s00493-024-00110-644:5(1115-1148)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s00493-024-00110-6

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents