The clique problem in ray intersection graphs. (English) Zbl 1365.05217
Epstein, Leah (ed.) et al., Algorithms – ESA 2012. 20th annual European symposium, Ljubljana, Slovenia, September 10–12, 2012. Proceeding. Berlin: Springer (ISBN 978-3-642-33089-6/pbk). Lecture Notes in Computer Science 7501, 241-252 (2012).
Summary: 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 J. Kratochvíl and J. Nešetřil [Commentat. Math. Univ. Carol. 31, No. 1, 85–93 (1990; Zbl 0727.05056)].
For the entire collection see [Zbl 1246.68031].
For the entire collection see [Zbl 1246.68031].
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
