The Clique Problem in Ray Intersection Graphs |
| |
| Authors: | Sergio Cabello Jean Cardinal Stefan Langerman |
| |
| Affiliation: | 1. Department of Mathematics, IMFM, FMF, University of Ljubljana, Ljubljana, Slovenia
2. Computer Science Department, Université Libre de Bruxelles (ULB), Brussels, Belgium
|
| |
| 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íl and Ne?et?il (Comment Math Univ Carolinae 31(1):85–93, 1990). |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
