The Clique Problem in Ray Intersection Graphs

2011/11/25 by Sergio Cabello, Cabello, Sergio, Jean Cardinal +3 · 2 citations
Computer Science · Engineering · #Computational Geometry and Mesh Generation #VLSI and FPGA Design Techniques #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.1111.5986

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.

Cited by

• Finding Cliques in Geometric Intersection Graphs with Grounded or Stabbed Constraints
• Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs

Related

• Finding Cliques in Geometric Intersection Graphs with Grounded or Stabbed Constraints
• Intersection Graphs of Rays and Grounded Segments
• Maximum Clique in Disk-Like Intersection Graphs
• Homothetic Polygons and Beyond: Intersection Graphs, Recognition, and Maximum Clique
• Segment Intersection Representations, Level Planarity and Constrained Ordering Problems