The Clique Problem in Ray Intersection Graphs

DOI10.1007/978-3-642-33090-2_22MaRDI QIDQ2912845zbMATH OpenOpenAlexFDO

Authors S. Cabello, Jean Cardinal, Stefan Langerman

Publication date 25 September 2012

Published in Algorithms – ESA 2012 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.5986

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Ray intersection graphs are intersection graphs of rays, or halflines, in the plane. We show that any planar graph has an even subdivision whose complement is a ray intersection graph. The construction can be done in polynomial time and implies that finding a maximum clique in a segment intersection graph is NP-hard. This solves a 21-year old open problem posed by Kratochv'il and Nev{s}etv{r}il.

Recommendations

• The clique problem in ray intersection graphs
• The clique problem in intersection graphs of ellipses and triangles
• scientific article; zbMATH DE number 1979524
• Intersection graphs and the clique operator
• scientific article; zbMATH DE number 798640
• Extremal graphs for intersecting cliques
• The maximum clique problem in multiple interval graphs
• scientific article; zbMATH DE number 4200260
• The maximum clique interdiction problem
• Clique chromatic numbers of intersection graphs

Cited in

(6)

• The clique problem in intersection graphs of ellipses and triangles
• Embedding ray intersection graphs and global curve simplification
• The maximum clique problem in multiple interval graphs
• The clique problem in ray intersection graphs
• scientific article; zbMATH DE number 1979524 (Why is no real title available?)
• Intersection graphs of rays and grounded segments

This page was built for publication: The Clique Problem in Ray Intersection Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2912845)