Seminario AGCO

The ACGO seminars are held every wednesday as part of an effort of a group of researchers around the topics of Algorithms, Combinatorics, Game Theory and Optimization. Our team consists of researchers in different disciplines and from several chilean universities. If you are interested in giving a talk or receiving the announcements of the seminars, please send us an email to jverschae followed by Webpage:

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.