The clique problem in ray intersection graphs

DOI10.1007/S00454-013-9538-5MaRDI QIDQ377488zbMATH OpenOpenAlexFDO

Authors S. Cabello, Jean Cardinal, Stefan Langerman

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

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)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1670809 (Why is no real title available?)
• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• Computing the independence number of intersection graphs
• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• Independent set of intersection graphs of convex objects in 2D
• Intersection graphs of segments
• On intersection representations of co-planar graphs
• On six problems posed by Jarik Nešetřil
• Segment representation of a subclass of co-planar graphs
• The Rectilinear Steiner Tree Problem is NP-Complete
• The clique problem in intersection graphs of ellipses and triangles
• The max clique problem in classes of string-graphs

Cited in

(23)

• 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
• Perfect matchings with crossings
• Complexity and polynomially solvable special cases of QUBO
• QPTAS and subexponential algorithm for maximum clique on disk graphs
• The Clique Problem in Ray Intersection Graphs
• scientific article; zbMATH DE number 7559254 (Why is no real title available?)
• Homothetic polygons and beyond: maximal cliques in intersection graphs
• Proper colorability of segment intersection graphs
• scientific article; zbMATH DE number 1979524 (Why is no real title available?)
• Sparse outerstring graphs have logarithmic treewidth
• On the chromatic number of disjointness graphs of curves
• On orthogonal ray trees
• Disjointness graphs of segments in the space
• Intersection graphs of rays and grounded segments
• Colored ray configurations
• 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)