2019/02/05 by Aamand, Anders, Abrahamsen, Mikkel, Knudsen, Jakob Bæk Tejs +1
#52C05 #Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1902.01732
Suppose that A is a convex body in the plane and that A1,…,An are 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.