Classifying convex bodies by their contact and intersection graphs

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


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 languageEnglish
Title of host publication37th International Symposium on Computational Geometry, SoCG 2021
EditorsKevin Buchin, Eric Colin de Verdiere
Number of pages16
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date2021
Article number3
ISBN (Electronic)9783959771849
Publication statusPublished - 2021
Event37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, United States
Duration: 7 Jun 202111 Jun 2021


Conference37th International Symposium on Computational Geometry, SoCG 2021
LandUnited States
ByVirtual, Buffalo
SeriesLeibniz International Proceedings in Informatics, LIPIcs

    Research areas

  • Contact graph, Convex body, Intersection graph

Number of downloads are based on statistics from Google Scholar and

No data available

ID: 273638044