2014/10/14 by Clemens Huemer, Huemer, Clemens, Pablo Pérez-Lantero +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG) #Point processes and geometric inequalities #cs.CG #math.MG
paper · pdf · doi:10.48550/arxiv.1410.4126
openalex publication_date 2014/10/14 · arxiv created 2016/06/16 · arxiv updated 2016/06/17 · openalex created_date 2022/12/15 · openalex updated_date 2026/08/04
Given a convex polygon of n sides, one can draw n disks (called side disks) where each disk has a different side of the polygon as diameter and the midpoint of the side as its center. The intersection graph of such disks is the undirected graph with vertices the n disks and two disks are adjacent if and only if they have a point in common. We prove that for every convex polygon this graph is planar. Particularly, for n=5, this shows that for any convex pentagon there are two disks among the five side disks that do not intersect, which means that K5 is never the intersection graph of such five disks. For n=6, we then have that for any convex hexagon the intersection graph of the side disks does not contain K3,3 as subgraph.