The clique problem in ray intersection graphs

DOI10.1007/S00454-013-9538-5zbMATH Open1275.05032OpenAlexW2047724597MaRDI QIDQ377488FDOQ377488

Jean Cardinal, Stefan Langerman, S. 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

Recommendations

• The Clique Problem in Ray Intersection Graphs
• scientific article
• Intersection graphs of rays and grounded segments
• Intersection graphs of rays and grounded segments
• The max clique problem in classes of string-graphs

zbMATH Keywords

maximum cliqueNP-hardnesssubdivisiongeometric intersection graphshalflinesray intersection graphrayssegment intersection graphs

Mathematics Subject Classification ID

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

Cites Work

• On six problems posed by Jarik Nešetřil
• The max clique problem in classes of string-graphs
• Intersection graphs of segments
• On intersection representations of co-planar graphs
• Segment representation of a subclass of co-planar graphs
• Every planar graph is the intersection graph of segments in the plane
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Independent set of intersection graphs of convex objects in 2D
• Title not available (Why is that?)
• The clique problem in intersection graphs of ellipses and triangles
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (23)

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

This page was built for publication: The clique problem in ray intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q377488)