The clique problem in ray intersection graphs

DOI10.1007/s00454-013-9538-5zbMath1275.05032OpenAlexW2047724597MaRDI QIDQ377488

Jean Cardinal, Stefan Langerman, Sergio Cabello

Publication date: 6 November 2013

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-013-9538-5

zbMATH Keywords

subdivisionNP-hardnessmaximum cliquegeometric intersection graphshalflinesray intersection graphrayssegment intersection graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Disjointness graphs of segments in the space ⋮ Intersection graphs of L-shapes and segments in the plane ⋮ Configurations of non-crossing rays and related problems ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ Perfect matchings with crossings ⋮ Homothetic polygons and beyond: maximal cliques in intersection graphs ⋮ Intersection Graphs of Rays and Grounded Segments ⋮ Proper colorability of segment intersection graphs ⋮ Colored ray configurations ⋮ On orthogonal ray trees ⋮ On the speed of algebraically defined graph classes ⋮ An algorithm for the maximum weight independent set problem on outerstring graphs ⋮ Perfect matchings with crossings ⋮ Unnamed Item ⋮ Grid intersection graphs and order dimension ⋮ Optimality program in segment and string graphs ⋮ Planar point sets determine many pairwise crossing segments ⋮ Unnamed Item ⋮ On the chromatic number of disjointness graphs of curves

Cites Work

• Segment representation of a subclass of co-planar graphs
• The max clique problem in classes of string-graphs
• Intersection graphs of segments
• On intersection representations of co-planar graphs
• The clique problem in intersection graphs of ellipses and triangles
• Independent set of intersection graphs of convex objects in 2D
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Every planar graph is the intersection graph of segments in the plane
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item