2018/05/28 by Luis H. Herrera, Herrera, Luis H., Pablo Pérez-Lantero +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Point processes and geometric inequalities #cs.CG
paper · pdf · doi:10.48550/arxiv.1805.10847
arxiv created 2018/05/28 · openalex publication_date 2018/05/28 · arxiv updated 2018/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a convex n-gon, we 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. Such a graph was introduced by Huemer and Pérez-Lantero in 2016, proved to be planar and Hamiltonian. In this paper we study further combinatorial properties of this graph. We prove that the treewidth is at most 3, by showing an O(n)-time algorithm that builds a tree decomposition of width at most 3, given the polygon as input. This implies that we can construct the intersection graph of the side disks in O(n) time. We further study the independence number of this graph, which is the maximum number of pairwise disjoint disks. The planarity condition implies that for every convex n-gon we can select at least \lceil n/4 \rceil pairwise disjoint disks, and we prove that for every n≥ 3 there exist convex n-gons in which we cannot select more than this number. Finally, we show that our class of graphs includes all outerplanar Hamiltonian graphs except the cycle of length four, and that it is a proper subclass of the planar Hamiltonian graphs.