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

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

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

Cited in

(5)

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)