2005/01/01 by Thomas Erlebach, Klaus Jansen, Eike Seidel · 2 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Unit disk graph #Combinatorics #Intersection graph #Mathematics #Chordal graph #Indifference graph #Disjoint sets #Maximal independent set #Planar graph #Pathwidth #Time complexity #Independent set #Discrete mathematics #Approximation algorithm #1-planar graph #Graph #Computer science #Line graph
paper · doi:10.1137/s0097539702402676
openalex publication_date 2005/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/03
A disk graph is the intersection graph of a set of disks with arbitrary diameters in the plane. For the case that the disk representation is given, we present polynomial-time approximation schemes (PTASs) for the maximum weight independent set problem (selecting disjoint disks of maximum total weight) and for the minimum weight vertex cover problem in disk graphs. These are the first known PTASs for NP-hard optimization problems on disk graphs. They are based on a novel recursive subdivision of the plane that allows applying a shifting strategy on different levels simultaneously, so that a dynamic programming approach becomes feasible. The PTASs for disk graphs represent a common generalization of previous results for planar graphs and unit disk graphs. They can be extended to intersection graphs of other "disk-like" geometric objects (such as squares or regular polygons), also in higher dimensions.