Pablo Pérez-Lantero, Usach.. Nucleo Milenio Información y Coordinación en Redes
The intersection graph of the disks with diameters the sides of a convex n-gon
U Chile (Beauchef), Av. República 701, DII.
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 K_5 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 K_3,3 as subgraph.