The Clique Problem in Ray Intersection Graphs

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).

• Publication year

  2011

• Venue

  Discrete & Computational Geometry

• Publication date

  2011-11-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00454-013-9538-5arXiv 1111.5986
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Computing the independence number of intersection graphs

  2011cited by this paper
• Segment representation of a subclass of co-planar graphs

  2010cited by this paper
• Every planar graph is the intersection graph of segments in the plane: extended abstract

  2009cited by this paper
• On Six Problems Posed by Jarik Nešetřil

  2006cited by this paper
• The Clique Problem in Intersection Graphs of Ellipses and Triangles

  2005cited by this paper
• Independent set of intersection graphs of convex objects in 2D

  2004cited by this paper
• Clique Is Hard to Approximate within n1-o(1)

  2000cited by this paper
• Clique is hard to approximate withinn1−ε

  1999cited by this paper
• On intersection representations of co-planar graphs

  1998cited by this paper
• Intersection Graphs of Segments

  1994cited by this paper
• The max clique problem in classes of string-graphs

  1992cited by this paper
• The Rectilinear Steiner Tree Problem is NP Complete

  1977influential reference

• Computing Maximum Cliques in Unit Disk Graphs

  2025cites this paper
• Finding Cliques in Geometric Intersection Graphs with Grounded or Stabbed Constraints

  2025cites this paper
• Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs

  2025cites this paper
• Crossing and Independent Families Among Polygons

  2025cites this paper
• Proper colorability of segment intersection graphs

  2024cites this paper
• Sparse Outerstring Graphs Have Logarithmic Treewidth

  2024cites this paper
• Approximating Densest Subgraph in Geometric Intersection Graphs

  2024cites this paper
• The Maximum Clique Problem in a Disk Graph Made Easy

  2024cites this paper
• Perfect Matchings with Crossings

  2023cites this paper
• Finding a Maximum Clique in a Disk Graph

  2023cites this paper
• Partitioning Geometric Graphs into Plane Subgraphs

  2022cites this paper
• EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs

  2021cites this paper
• What Makes the Recognition Problem Hard for Classes Related to Segment and String graphs?

  2021cites this paper
• Finding a Maximum Clique in a Grounded 1-Bend String Graph

  2021cites this paper
• Maximum Clique in Disk-Like Intersection Graphs

  2020cites this paper
• Planar point sets determine many pairwise crossing segments

  2019cites this paper
• On the speed of algebraically defined graph classes

  2019cites this paper
• Colored Ray Configurations

  2018cites this paper
• Homothetic polygons and beyond: Maximal cliques in intersection graphs

  2018cites this paper
• On the Chromatic Number of Disjointness Graphs of Curves

  2018cites this paper
• Grid Intersection Graphs and Order Dimension

  2018cites this paper
• QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs

  2017cites this paper
• Restricted String Representations

  2017cites this paper
• Disjointness Graphs of Segments

  2017cites this paper
• Optimality Program in Segment and String Graphs

  2017cites this paper
• Relay Placement in Wireless Networks: Minimizing Communication Cost

  2016cites this paper
• Splitting B_2 -VPG Graphs into Outer-String and Co-Comparability Graphs

  2016cites this paper
• Intersection graphs and geometric objects in the plane

  2016cites this paper
• Intersection Graphs and Geometric Objects in the Plane

  2016cites this paper
• Configurations of Non-crossing Rays and Related Problems

  2016cites this paper
• Intersection Graphs of Rays and Grounded Segments

  2016cites this paper
• Configurations of Non-crossing Rays and Related Problems

  2016cites this paper
• Coloring segment intersection graphs avoiding monochromatic cliques Proposer :

  2015cites this paper
• Deposited in DRO : 17 September 2014 Version of attached le : Accepted Version Peer-review status of attached

  2015cites this paper
• Grid Intersection Graphs and Order Dimension

  2015cites this paper
• An Algorithm for the Maximum Weight Independent Set Problem onOutersting Graphs

  2015cites this paper
• On Intersection Graphs of Convex Polygons

  2014cites this paper
• On subclasses of grid intersection graphs

  2014cites this paper
• Homothetic Polygons and Beyond: Intersection Graphs, Recognition, and Maximum Clique

  2014cites this paper
• Knapsack Intersection Graphs and Efficient Computation of Their Maximal Cliques

  2014cites this paper
• Intersection graphs of L-shapes and segments in the plane

  2014cites this paper
• A Polynomial time Algorithm for the Maximum Weight Independent Set Problem on Outerstring Graphs ∗

  2013cites this paper
• On the Recognition of Four-Directional Orthogonal Ray Graphs

  2013cites this paper
• On orthogonal ray trees

  2013cites this paper
• Data Reduction and Problem Kernels (Dagstuhl Seminar 12241)

  2012cites this paper
• Beyond Homothetic Polygons: Recognition and Maximum Clique

  2012cites this paper
• The Maximum Clique Problem in Multiple Interval Graphs

  2011cites this paper
• City Research Online

  year unknowncites this paper