2026-07-22T01:18:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13802 2024-03-06T10:52:45Z ddc:004 open_access

Classifying Convex Bodies by Their Contact and Intersection Graphs Aamand, Anders Abrahamsen, Mikkel Knudsen, Jakob Bæk Tejs Rasmussen, Peter Michael Reichstein convex body contact graph intersection graph 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anders Aamand and Mikkel Abrahamsen and Jakob Bæk Tejs Knudsen and Peter Michael Reichstein Rasmussen 2021 Is Part Of LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2021.3 urn:nbn:de:0030-drops-138024 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.3 eng https://creativecommons.org/licenses/by/4.0/legalcode