Document Open Access Logo

Classifying Convex Bodies by Their Contact and Intersection Graphs

Authors Anders Aamand , Mikkel Abrahamsen , Jakob Bæk Tejs Knudsen , Peter Michael Reichstein Rasmussen

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.3.pdf
  • Filesize: 1.23 MB
  • 16 pages

Document Identifiers

Author Details

Anders Aamand
  • BARC, University of Copenhagen, Denmark
Mikkel Abrahamsen
  • BARC, University of Copenhagen, Denmark
Jakob Bæk Tejs Knudsen
  • BARC, University of Copenhagen, Denmark
Peter Michael Reichstein Rasmussen
  • BARC, University of Copenhagen, Denmark

Funding

The authors are part of BARC, Basic Algorithms Research Copenhagen, supported by the VILLUM Foundation grant 16582.

Acknowledgements

We thank Tillmann Miltzow for asking when the translates of two different convex bodies induce the same intersection graphs which inspired us to work on these problems.

Cite AsGet BibTex

Anders Aamand, Mikkel Abrahamsen, Jakob Bæk Tejs Knudsen, and Peter Michael Reichstein Rasmussen. Classifying Convex Bodies by Their Contact and Intersection Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.3

Abstract

Let A be a convex body in the plane and A₁,…,A_n be translates of A. Such translates give rise to an intersection graph of A, G = (V,E), with vertices V = {1,… ,n} and edges E = {uv∣ A_u ∩ A_v ≠ ∅}. The subgraph G' = (V, E') satisfying that E' ⊂ E is the set of edges uv for which the interiors of A_u and A_v are disjoint is a unit distance graph of A. If furthermore G' = G, i.e., if the interiors of A_u and A_v are disjoint whenever u≠ v, then G is a contact graph of A. In this paper, we study which pairs of convex bodies have the same contact, unit distance, or intersection graphs. We say that two convex bodies A and B are equivalent if there exists a linear transformation B' of B such that for any slope, the longest line segments with that slope contained in A and B', respectively, are equally long. For a broad class of convex bodies, including all strictly convex bodies and linear transformations of regular polygons, we show that the contact graphs of A and B are the same if and only if A and B are equivalent. We prove the same statement for unit distance and intersection graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Graph theory
  • Mathematics of computing → Discrete mathematics
Keywords
  • convex body
  • contact graph
  • intersection graph

Metrics

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

Related Versions

References

  1. Anders Aamand, Mikkel Abrahamsen, Jakob Bæk Tejs Knudsen, and Peter Michael Reichstein Rasmussen. Classifying convex bodies by their contact and intersection graphs, 2019. Preprint. URL: http://arxiv.org/abs/1902.01732.
  2. Édouard Bonnet, Nicolas Grelier, and Tillmann Miltzow. Maximum clique in disk-like intersection graphs. Preprint, 2020. URL: http://arxiv.org/abs/2003.02583.
  3. Károly Böröczky Jr. Finite packing and covering, volume 154 of Cambridge Tracts in Mathematics. Cambridge University Press, 2004. Google Scholar
  4. Sergio Cabello and Miha Jejčič. Refining the hierarchies of classes of geometric intersection graphs. The Electronic Journal of Combinatorics, 24(1):1-19, 2017. Google Scholar
  5. Jean Cardinal. Computational geometry column 62. SIGACT News, 46(4):69-78, 2015. Google Scholar
  6. Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, and Birgit Vogtenhuber. Intersection graphs of rays and grounded segments. In Hans L. Bodlaender and Gerhard J. Woeginger, editors, Graph-Theoretic Concepts in Computer Science, pages 153-166, Cham, 2017. Springer International Publishing. Google Scholar
  7. Timothy M. Chan and Dimitrios Skrepetos. Approximate shortest paths and distance oracles in weighted unit-disk graphs. Journal of Computational Geometry, 10(2), 2019. Google Scholar
  8. Steven Chaplick, Stefan Felsner, Udo Hoffmann, and Veit Wiechert. Grid intersection graphs and order dimension. Order, 35:363-391, 2018. Google Scholar
  9. Brent N. Clark, Charles J. Colbourn, and David S. Johnson. Unit disk graphs. Discrete Mathematics, 86(1-3):165-177, 1990. Google Scholar
  10. László Fejes Tóth. Lagerungen in der Ebene auf der Kugel und im Raum, volume 65 of Die Grundlehren der mathematischen Wissenschaften. Springer, second edition, 1972. Google Scholar
  11. Stefan Felsner and Günter Rote. On primal-dual circle representations. In 34th European Workshop on Computational Geometry (EuroCG 2018), pages 72:1-72:6, 2018. Google Scholar
  12. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Finding, hitting and packing cycles in subexponential time on unit disk graphs. Discrete & Computational Geometry, 62(4):879-911, 2019. Google Scholar
  13. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs. In 36th International Symposium on Computational Geometry (SoCG 2020), pages 44:1-44:18, 2020. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.44.
  14. Stefan Funke, Alexander Kesselman, Ulrich Meyer, and Michael Segal. A simple improved distributed algorithm for minimum CDS in unit disk graphs. ACM Transactions on Sensor Networks, 2(3):444–453, 2006. URL: https://doi.org/10.1145/1167935.1167941.
  15. György Pál Gehér. A contribution to the Aleksandrov conservative distance problem in two dimensions. Linear Algebra and its Applications, 481:280-287, 2015. Google Scholar
  16. Albert Gräf, Martin Stumpf, and Gerhard Weißenfels. On coloring unit disk graphs. Algorithmica, 20(3):277-293, 1998. Google Scholar
  17. Svante Janson and Jan Kratochvíl. Thresholds for classes of intersection graphs. Discrete Mathematics, 108:307-326, 1992. Google Scholar
  18. Victor Klee. Some new results on smoothness and rotundity in normed linear spaces. Mathematische Annalen, 139(1):51-63, 1959. Google Scholar
  19. P. Koebe. Kontaktprobleme der konformen Abbildung. Berichte über die Verhandlungen der Sächsische Akademie der Wissenschaften zu Leipzig, Mathematisch-Physische Klasse, 88:141-164, 1936. Google Scholar
  20. Jan Kratochivíl and Jiří Matoušek. Intersection graphs of segments. Journal of Combinatorial Theory Series B, 62(2):289-315, 1994. Google Scholar
  21. M. V. Marathe, H. Breu, H. B. Hunt III, S. S. Ravi, and D. J. Rosenkrantz. Simple heuristics for unit disk graphs. Networks, 25(2):59-68, 1995. URL: https://doi.org/10.1002/net.3230250205.
  22. Colin McDiarmid and Tobias Müller. Integer realizations of disk and segment graphs. Journal of Combinatorial Theory, Series B, 103(1):114-143, 2013. Google Scholar
  23. Tobias Müller, Erik Jan van Leeuwen, and Jan van Leeuwen. Integer representations of convex polygon intersection graphs. SIAM Journal on Discrete Mathematics, 27(1):205-231, 2013. Google Scholar
  24. Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pages 1035-1054, 2019. Google Scholar
  25. Marco A. Peyrot-Solís, Giselle M. Galvan-Tejada, and Hildeberto Jardon-Aguilar. Proposal of a planar directional UWB antenna for any desired operational bandwidth. International Journal of Antennas and Propagation, 2014:1-12, 2014. Google Scholar
  26. Oded Schramm. Combinatorically prescribed packings and applications to conformal and quasiconformal maps. Preprint, 2007. URL: http://arxiv.org/abs/0709.0710.
  27. Konrad Swanepoel. Combinatorial distance geometry in normed spaces. In Gergely Ambrus, Imre Bárány, Károly J. Böröczky, Gábor Fejes Tóth, and János Pach, editors, New Trends in Intuitive Geometry, volume 27 of Bolyai Society Mathematical Studies. Springer, 2018. Google Scholar
  28. G. Fejes Tóth. New Results in the Theory of Packing and Covering, pages 318-359. Birkhäuser Basel, Basel, 1983. URL: https://doi.org/10.1007/978-3-0348-5858-8_14.
  29. Weili Wu, Hongwei Du, Xiaohua Jia, Yingshu Li, and Scott C-H Huang. Minimum connected dominating sets and maximal independent sets in unit disk graphs. Theoretical Computer Science, 352(1-3):1-7, 2006. Google Scholar
  30. Tudor Zamfirescu. Nearly all convex bodies are smooth and strictly convex. Monatshefte für Mathematik, 103(1):57-62, 1987. 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