Classifying convex bodies by their contact and intersection graphs
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Classifying Convex Bodies by Their Contact and Intersection Graphs
Final published version, 1.23 MB, PDF document
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 |
---|---|
Title of host publication | 37th International Symposium on Computational Geometry, SoCG 2021 |
Editors | Kevin Buchin, Eric Colin de Verdiere |
Number of pages | 16 |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publication date | 2021 |
Article number | 3 |
ISBN (Electronic) | 9783959771849 |
DOIs | |
Publication status | Published - 2021 |
Event | 37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, United States Duration: 7 Jun 2021 → 11 Jun 2021 |
Conference
Conference | 37th International Symposium on Computational Geometry, SoCG 2021 |
---|---|
Land | United States |
By | Virtual, Buffalo |
Periode | 07/06/2021 → 11/06/2021 |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 189 |
ISSN | 1868-8969 |
- Contact graph, Convex body, Intersection graph
Research areas
Number of downloads are based on statistics from Google Scholar and www.ku.dk
ID: 273638044