The Clique problem in intersection graphs of ellipses and triangles Journal Article

Author(s): Ambühl, Christoph; Wagner, Uli
Article Title: The Clique problem in intersection graphs of ellipses and triangles
Abstract: Intersection graphs of disks and of line segments, respectively, have been well studied, because of both practical applications and theoretically interesting properties of these graphs. Despite partial results, the complexity status of the Clique problem for these two graph classes is still open. Here, we consider the Clique problem for intersection graphs of ellipses, which, in a sense, interpolate between disks and line segments, and show that the problem is APX-hard in that case. Moreover, this holds even if for all ellipses, the ratio of the larger over the smaller radius is some prescribed number. Furthermore, the reduction immediately carries over to intersection graphs of triangles. To our knowledge, this is the first hardness result for the Clique problem in intersection graphs of convex objects with finite description complexity. We also describe a simple approximation algorithm for the case of ellipses for which the ratio of radii is bounded.
Keywords: line segments; Clique problem; Convex objects; Intersection graphs
Journal Title: Theory of Computing Systems
Volume: 38
Issue 3
ISSN: 1433-0490
Publisher: Springer  
Date Published: 2005-05-01
Start Page: 279
End Page: 292
DOI: 10.1007/s00224-005-1141-6
Open access: no
IST Austria Authors
  1. Uli Wagner
    50 Wagner
Related IST Austria Work