Document Open Access Logo

Graph Product Structure for h-Framed Graphs

Authors Michael A. Bekos , Giordano Da Lozzo , Petr Hliněný , Michael Kaufmann

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.23.pdf
  • Filesize: 1.13 MB
  • 15 pages

Document Identifiers

Author Details

Michael A. Bekos
  • University of Ioannina, Greece
Giordano Da Lozzo
  • Roma Tre University, Rome, Italy
Petr Hliněný
  • Masaryk University, Brno, Czech Republic
Michael Kaufmann
  • Universität Tübingen, Germany

Funding

  • Da Lozzo, Giordano: Supported in part by MIUR Project "AHeAD" under PRIN 20174LF3T8.
  • Hliněný, Petr: Supported by the Czech Science Foundation, project no. 20-04567S.
  • Kaufmann, Michael: Supported in part by DFG Ka 812-18/2.

Acknowledgements

This research started at the Dagstuhl Seminar 21293 "Parameterized Complexity in Graph Drawing", July 18 - 23, 2021 [Robert Ganian et al., 2021].

Cite As Get BibTex

Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný, and Michael Kaufmann. Graph Product Structure for h-Framed Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ISAAC.2022.23

Abstract

Graph product structure theory expresses certain graphs as subgraphs of the strong product of much simpler graphs. In particular, an elegant formulation for the corresponding structural theorems involves the strong product of a path and of a bounded treewidth graph, and allows to lift combinatorial results for bounded treewidth graphs to graph classes for which the product structure holds, such as to planar graphs [Dujmović et al., J. ACM, 67(4), 22:1-38, 2020].
In this paper, we join the search for extensions of this powerful tool beyond planarity by considering the h-framed graphs, a graph class that includes 1-planar, optimal 2-planar, and k-map graphs (for appropriate values of h). We establish a graph product structure theorem for h-framed graphs stating that the graphs in this class are subgraphs of the strong product of a path, of a planar graph of treewidth at most 3, and of a clique of size 3⌊ h/2 ⌋+⌊ h/3 ⌋-1. This allows us to improve over the previous structural theorems for 1-planar and k-map graphs. Our results constitute significant progress over the previous bounds on the queue number, non-repetitive chromatic number, and p-centered chromatic number of these graph classes, e.g., we lower the currently best upper bound on the queue number of 1-planar graphs and k-map graphs from 115 to 82 and from ⌊ 33/2(k+3 ⌊ k/2⌋ -3)⌋ to ⌊ 33/2 (3⌊ k/2 ⌋+⌊ k/3 ⌋-1) ⌋, respectively. We also employ the product structure machinery to improve the current upper bounds on the twin-width of 1-planar graphs from O(1) to 80. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
  • Mathematics of computing → Graphs and surfaces
Keywords
  • Graph product structure theory
  • h-framed graphs
  • k-map graphs
  • queue number
  • twin-width

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

  • Complete proofs of statements marked with (*) in the main part can be found in the extended version of this document:
  • Extended Version https://arxiv.org/abs/2204.11495

References

  1. Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann, Michael Kaufmann, and Sergey Pupyrev. Queue layouts of planar 3-trees. Algorithmica, 82(9):2564-2585, 2020. URL: https://doi.org/10.1007/s00453-020-00697-4.
  2. Md. Jawaherul Alam, Franz J. Brandenburg, and Stephen G. Kobourov. Straight-line grid drawings of 3-connected 1-planar graphs. In Stephen K. Wismath and Alexander Wolff, editors, Graph Drawing, volume 8242 of LNCS, pages 83-94. Springer, 2013. URL: https://doi.org/10.1007/978-3-319-03841-4_8.
  3. Michael A. Bekos, Giordano Da Lozzo, Svenja Griesbach, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi N. Raftopoulou. Book embeddings of nonplanar graphs with small faces in few pages. CoRR, abs/2003.07655, 2020. URL: http://arxiv.org/abs/2003.07655.
  4. Michael A. Bekos, Michael Kaufmann, and Chrysanthi N. Raftopoulou. On optimal 2- and 3-planar graphs. In Boris Aronov and Matthew J. Katz, editors, SoCG, volume 77 of LIPIcs, pages 16:1-16:16. Schloss Dagstuhl, 2017. URL: https://doi.org/10.4230/LIPIcs.SoCG.2017.16.
  5. Michael A. Bekos, Giordano Da Lozzo, Svenja Griesbach, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi N. Raftopoulou. Book embeddings of nonplanar graphs with small faces in few pages. In SoCG, volume 164 of LIPIcs, pages 16:1-16:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  6. Michael A. Bekos, Giordano Da Lozzo, Petr Hlinený, and Michael Kaufmann. Graph product structure for h-framed graphs. CoRR, abs/2204.11495, 2022. URL: http://arxiv.org/abs/2204.11495.
  7. Marthe Bonamy, Cyril Gavoille, and Michal Pilipczuk. Shorter labeling schemes for planar graphs. In Shuchi Chawla, editor, SODA, pages 446-462. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.27.
  8. Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking. J. ACM, 69(1):3:1-3:46, 2022. Google Scholar
  9. Édouard Bonnet, O-joung Kwon, and David R. Wood. Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond). CoRR, abs/2202.11858, 2022. URL: http://arxiv.org/abs/2202.11858.
  10. Prosenjit Bose, Pat Morin, and Saeed Odak. An optimal algorithm for product structure in planar graphs. CoRR, abs/2202.08870, 2022. URL: http://arxiv.org/abs/2202.08870.
  11. Michal Debski, Stefan Felsner, Piotr Micek, and Felix Schröder. Improved bounds for centered colorings. In Shuchi Chawla, editor, SODA, pages 2212-2226. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.136.
  12. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  13. Vida Dujmovic, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, and Pat Morin. Adjacency labelling for planar graphs (and beyond). In FOCS. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00060.
  14. Vida Dujmovic, Louis Esperet, Pat Morin, Bartosz Walczak, and David R. Wood. Clustered 3-colouring graphs of bounded degree. Comb. Probab. Comput., 31(1):123-135, 2022. URL: https://doi.org/10.1017/S0963548321000213.
  15. Vida Dujmovic, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood. Planar graphs have bounded queue-number. J. ACM, 67(4):22:1-22:38, 2020. URL: https://doi.org/10.1145/3385731.
  16. Vida Dujmovic, Pat Morin, and David R. Wood. Graph product structure for non-minor-closed classes. CoRR, abs/1907.05168v3, 2020. URL: http://arxiv.org/abs/1907.05168v3.
  17. Vida Dujmovic, Pat Morin, and David R. Wood. Graph product structure for non-minor-closed classes. CoRR, abs/1907.05168v4, April 2022. URL: http://arxiv.org/abs/1907.05168v4.
  18. Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, and David Wood. Planar graphs have bounded nonrepetitive chromatic number. Advances in Combinatorics, March 2020. URL: https://doi.org/10.19086/aic.12100.
  19. Zdenek Dvořák, Tony Huynh, Gwenaël Joret, Chun-Hung Liu, and David R. Wood. Notes on graph product structure theory. CoRR, abs/2001.08860, 2020. URL: http://arxiv.org/abs/2001.08860.
  20. Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg, and Meirav Zehavi. Parameterized complexity in graph drawing (dagstuhl seminar 21293). Dagstuhl Reports, 11(6):82-123, 2021. URL: https://doi.org/10.4230/DagRep.11.6.82.
  21. Lenwood S. Heath, Frank Thomson Leighton, and Arnold L. Rosenberg. Comparing queues and stacks as mechanisms for laying out graphs. SIAM J. Discrete Math., 5(3):398-412, 1992. URL: https://doi.org/10.1137/0405031.
  22. Petr Hliněný. Twin-width of planar graphs is at most 9. CoRR, abs/2205.05378, 2022. URL: http://arxiv.org/abs/2205.05378.
  23. Hugo Jacob and Marcin Pilipczuk. Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs. CoRR, abs/2201.09749, 2022. URL: http://arxiv.org/abs/2201.09749.
  24. Pat Morin. A fast algorithm for the product structure of planar graphs. Algorithmica, 83(5):1544-1558, 2021. URL: https://doi.org/10.1007/s00453-020-00793-5.
  25. Pat Morin, Vida Dujmović, Sergey Norin, and David Wood. Graph product structure theory. Banff Int., November 21-26 2021. Google Scholar
  26. Michal Pilipczuk and Sebastian Siebertz. Polynomial bounds for centered colorings on proper minor-closed graph classes. J. Comb. Theory, Ser. B, 151:111-147, 2021. URL: https://doi.org/10.1016/j.jctb.2021.06.002.
  27. Torsten Ueckerdt, David R. Wood, and Wendy Yi. An improved planar graph product structure theorem. CoRR, abs/2108.00198, 2021. URL: http://arxiv.org/abs/2108.00198.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact