文章基本信息
- 标题：Classifying Convex Bodies by Their Contact and Intersection Graphs
- 本地全文：下载
- 作者：Aamand, Anders ; Abrahamsen, Mikkel ; Knudsen, Jakob B{ e}k Tejs 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2021
- 卷号：189
- 页码：3:1-3:16
- DOI：10.4230/LIPIcs.SoCG.2021.3
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：Let A be a convex body in the plane and Aâ,,â¦,A_n 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â^£ A_u â^© A_v â â^.}. The subgraph G' = (V, E') satisfying that E' âS, E is the set of edges uv for which the interiors of A_u and A_v are disjoint is a unit distance graph of A. If furthermore G' = G, i.e., if the interiors of A_u and A_v 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.
- 关键词：convex body; contact graph; intersection graph
