---
_id: '2421'
abstract:
- lang: eng
  text: 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 disc and ellipses, and show that it 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. To our knowledge, this is the first hardness
    result for the Clique problem in intersection graphs of 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.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Christoph
  full_name: Ambühl, Christoph
  last_name: Ambühl
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: 'Ambühl C, Wagner U. On the Clique problem in intersection graphs of ellipses.
    In: <i>Proceedings of the 13th International Symposium on Algorithms and Computation</i>.
    Vol 2518. Springer; 2002:489-500. doi:<a href="https://doi.org/10.1007/3-540-36136-7_43">10.1007/3-540-36136-7_43</a>'
  apa: 'Ambühl, C., &#38; Wagner, U. (2002). On the Clique problem in intersection
    graphs of ellipses. In <i>Proceedings of the 13th International Symposium on Algorithms
    and Computation</i> (Vol. 2518, pp. 489–500). Vancouver, Canada: Springer. <a
    href="https://doi.org/10.1007/3-540-36136-7_43">https://doi.org/10.1007/3-540-36136-7_43</a>'
  chicago: Ambühl, Christoph, and Uli Wagner. “On the Clique Problem in Intersection
    Graphs of Ellipses.” In <i>Proceedings of the 13th International Symposium on
    Algorithms and Computation</i>, 2518:489–500. Springer, 2002. <a href="https://doi.org/10.1007/3-540-36136-7_43">https://doi.org/10.1007/3-540-36136-7_43</a>.
  ieee: C. Ambühl and U. Wagner, “On the Clique problem in intersection graphs of
    ellipses,” in <i>Proceedings of the 13th International Symposium on Algorithms
    and Computation</i>, Vancouver, Canada, 2002, vol. 2518, pp. 489–500.
  ista: 'Ambühl C, Wagner U. 2002. On the Clique problem in intersection graphs of
    ellipses. Proceedings of the 13th International Symposium on Algorithms and Computation.
    ISAAC: International Symposium on Algorithms and Computation, LNCS, vol. 2518,
    489–500.'
  mla: Ambühl, Christoph, and Uli Wagner. “On the Clique Problem in Intersection Graphs
    of Ellipses.” <i>Proceedings of the 13th International Symposium on Algorithms
    and Computation</i>, vol. 2518, Springer, 2002, pp. 489–500, doi:<a href="https://doi.org/10.1007/3-540-36136-7_43">10.1007/3-540-36136-7_43</a>.
  short: C. Ambühl, U. Wagner, in:, Proceedings of the 13th International Symposium
    on Algorithms and Computation, Springer, 2002, pp. 489–500.
conference:
  end_date: 2002-11-23
  location: Vancouver, Canada
  name: 'ISAAC: International Symposium on Algorithms and Computation'
  start_date: 2002-11-21
date_created: 2018-12-11T11:57:34Z
date_published: 2002-01-01T00:00:00Z
date_updated: 2023-07-25T11:48:36Z
day: '01'
doi: 10.1007/3-540-36136-7_43
extern: '1'
intvolume: '      2518'
language:
- iso: eng
month: '01'
oa_version: None
page: 489 - 500
publication: Proceedings of the 13th International Symposium on Algorithms and Computation
publication_identifier:
  isbn:
  - '9783540001423'
publication_status: published
publisher: Springer
publist_id: '4504'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the Clique problem in intersection graphs of ellipses
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2518
year: '2002'
...