Document Open Access Logo

On Comparable Box Dimension

Authors Zdeněk Dvořák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, Torsten Ueckerdt

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.38.pdf
  • Filesize: 0.63 MB
  • 14 pages

Document Identifiers

Author Details

Zdeněk Dvořák
  • Charles University, Prague, Czech Republic
Daniel Gonçalves
  • LIRMM, Université de Montpellier, CNRS, Montpellier, France
Abhiruk Lahiri
  • Charles University, Prague, Czech Republic
Jane Tan
  • Mathematical Institute, University of Oxford, UK
Torsten Ueckerdt
  • Karlsruhe Institute of Technology, Germany

Funding

  • Dvořák, Zdeněk: Supported by the ERC-CZ project LL2005 (Algorithms and complexity within and beyond bounded expansion) of the Ministry of Education of Czech Republic.
  • Gonçalves, Daniel: Supported by the ANR grant GATO ANR-16-CE40-0009.
  • Lahiri, Abhiruk: Supported by the ERC-CZ project LL2005 (Algorithms and complexity within and beyond bounded expansion) of the Ministry of Education of Czech Republic.

Acknowledgements

This research was carried out at the workshop on Geometric Graphs and Hypergraphs organized by Yelena Yuditsky and Torsten Ueckerdt in September 2021. We would like to thank the organizers and all participants for creating a friendly and productive environment.

Cite AsGet BibTex

Zdeněk Dvořák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt. On Comparable Box Dimension. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.38

Abstract

Two boxes in ℝ^d are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph G is the minimum integer d such that G can be represented as a touching graph of comparable axis-aligned boxes in ℝ^d. We show that proper minor-closed classes have bounded comparable box dimension and explore further properties of this notion.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Graphs and surfaces
Keywords
  • geometric graphs
  • minor-closed graph classes
  • treewidth fragility

Metrics

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

Related Versions

References

  1. Michael O Albertson, Glenn G Chappell, Hal A Kierstead, André Kündgen, and Radhika Ramamurthi. Coloring with no 2-colored p_4’s. the electronic journal of combinatorics, pages R26-R26, 2004. Google Scholar
  2. B.S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM (JACM), 41(1):153-180, 1994. Google Scholar
  3. E. Berger, Z. Dvořák, and S. Norin. Treewidth of grid subsets. Combinatorica, 2017. Accepted, URL: https://doi.org/10.1007/s00493-017-3548-5.
  4. V. Dujmović, G. Joret, P. Micek, P. Morin, T. Ueckerdt, and D. R. Wood. Planar graphs have bounded queue-number. Journal of the ACM, 67:22, 2020. Google Scholar
  5. Z. Dvořák. Sublinear separators, fragility and subexponential expansion. European Journal of Combinatorics, 52:103-119, 2016. Google Scholar
  6. Z. Dvořák, R. McCarty, and S. Norin. Sublinear separators in intersection graphs of convex shapes. arXiv, 2001.01552, 2020. URL: http://arxiv.org/abs/2001.01552.
  7. Zdenek Dvorák. Approximation metatheorem for fractionally treewidth-fragile graphs. arXiv, 2103.08698, 2021. URL: http://arxiv.org/abs/2103.08698.
  8. Zdenek Dvorák and Abhiruk Lahiri. Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs. In 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 40:1-40:10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  9. Zdeněk Dvořák, Jakub Pekárek, Torsten Ueckerdt, and Yelena Yuditsky. Weak coloring numbers of intersection graphs. arXiv, 2103.17094, 2021. URL: http://arxiv.org/abs/2103.17094.
  10. Thomas Erlebach, Klaus Jansen, and Eike Seidel. Polynomial-time approximation schemes for geometric intersection graphs. SIAM Journal on Computing, 34:1302-1323, 2005. Google Scholar
  11. Stefan Felsner and Mathew C Francis. Contact representations of planar graphs with cubes. In Proceedings of the twenty-seventh annual symposium on Computational geometry, pages 315-320, 2011. Google Scholar
  12. Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos Stavropoulos. Coloring and covering nowhere dense graphs. SIAM Journal on Discrete Mathematics, 32:2467-2481, 2018. Google Scholar
  13. P. Koebe. Kontaktprobleme der Konformen Abbildung. Math.-Phys. Kl., 88:141-164, 1936. Google Scholar
  14. L. Lovász. Graphs and Geometry. American Mathematical Society, Providence, 2019. Google Scholar
  15. J. Nešetřil and P. Ossona de Mendez. Sparsity (Graphs, Structures, and Algorithms), volume 28 of Algorithms and Combinatorics. Springer, 2012. Google Scholar
  16. Serge Plotkin, Satish Rao, and Warren D Smith. Shallow excluded minors and improved graph decompositions. In Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, pages 462-470. Society for Industrial and Applied Mathematics, 1994. Google Scholar
  17. N. Robertson and P. D. Seymour. Graph Minors. XVI. Excluding a non-planar graph. J. Combin. Theory, Ser. B, 89(1):43-76, 2003. Google Scholar
  18. Neil Robertson and Paul D. Seymour. Graph Minors. III. Planar tree-width. Journal of Combinatorial Theory, Series B, 36:49-64, 1984. Google Scholar
  19. Horst Sachs. Coin graphs, polyhedra, and conformal mapping. Discrete Mathematics, 134:133-138, 1994. Google Scholar
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 Imprint Privacy Contact