## Classifying convex bodies by their contact and intersection graphs

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

### Documents

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.

Original language English 37th International Symposium on Computational Geometry, SoCG 2021 Kevin Buchin, Eric Colin de Verdiere 16 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing 2021 3 9783959771849 https://doi.org/10.4230/LIPIcs.SoCG.2021.3 Published - 2021 37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, United StatesDuration: 7 Jun 2021 → 11 Jun 2021

### Conference

Conference 37th International Symposium on Computational Geometry, SoCG 2021 United States Virtual, Buffalo 07/06/2021 → 11/06/2021
Series Leibniz International Proceedings in Informatics, LIPIcs 189 1868-8969

### Research areas

• Contact graph, Convex body, Intersection graph

### Number of downloads are based on statistics from Google Scholar and www.ku.dk

No data available

ID: 273638044