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

geometric intersection graphshalflinesmaximum cliqueNP-hardnessray intersection graphrayssegment intersection graphssubdivision

Mathematics Subject Classification ID

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

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

• Computing the independence number of intersection graphs
• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• scientific article; zbMATH DE number 1670809 (Why is no real title available?)
• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• 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 clique problem in intersection graphs of ellipses and triangles
• The max clique problem in classes of string-graphs
• The Rectilinear Steiner Tree Problem is NP-Complete

Cited in

(28)

• Homothetic polygons and beyond: maximal cliques in intersection graphs
• Colored ray configurations
• The clique problem in intersection graphs of ellipses and triangles
• Embedding ray intersection graphs and global curve simplification
• Perfect matchings with crossings
• On the speed of algebraically defined graph classes
• Intersection graphs of L-shapes and segments in the plane
• Configurations of non-crossing rays and related problems
• The Clique Problem in Ray Intersection Graphs
• scientific article; zbMATH DE number 1979524 (Why is no real title available?)
• Intersection graphs of rays and grounded segments
• Complexity and polynomially solvable special cases of QUBO
• On the chromatic number of disjointness graphs of curves
• QPTAS and subexponential algorithm for maximum clique on disk graphs
• Disjointness graphs of segments in the space
• Optimality program in segment and string graphs
• Perfect matchings with crossings
• Proper colorability of segment intersection graphs
• Proper colorability of segment intersection graphs
• An algorithm for the maximum weight independent set problem on outerstring graphs
• Grid intersection graphs and order dimension
• Sparse outerstring graphs have logarithmic treewidth
• Approximating densest subgraph in geometric intersection graphs
• Crossing and independent families among polygons
• The maximum clique problem in a disk graph made easy
• Computing maximum cliques in unit disk graphs
• On the chromatic number of disjointness graphs of curves
• On orthogonal ray trees

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)