TY - GEN

T1 - Classifying convex bodies by their contact and intersection graphs

AU - Aamand, Anders

AU - Abrahamsen, Mikkel

AU - Knudsen, Jakob Bæk Tejs

AU - Rasmussen, Peter Michael Reichstein

PY - 2021

Y1 - 2021

N2 - Let A be a convex body in the plane and A1,..., An 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 | Au ∩Av ≠ ∅}. The subgraph G′ = (V, E′) satisfying that E′ ⊂ E is the set of edges uv for which the interiors of Au and Av are disjoint is a unit distance graph of A. If furthermore G′ = G, i.e., if the interiors of Au and Av 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.

AB - Let A be a convex body in the plane and A1,..., An 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 | Au ∩Av ≠ ∅}. The subgraph G′ = (V, E′) satisfying that E′ ⊂ E is the set of edges uv for which the interiors of Au and Av are disjoint is a unit distance graph of A. If furthermore G′ = G, i.e., if the interiors of Au and Av 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.

KW - Contact graph

KW - Convex body

KW - Intersection graph

U2 - 10.4230/LIPIcs.SoCG.2021.3

DO - 10.4230/LIPIcs.SoCG.2021.3

M3 - Article in proceedings

AN - SCOPUS:85108217218

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 37th International Symposium on Computational Geometry, SoCG 2021

A2 - Buchin, Kevin

A2 - de Verdiere, Eric Colin

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 37th International Symposium on Computational Geometry, SoCG 2021

Y2 - 7 June 2021 through 11 June 2021

ER -