On rectangle intersection and overlap graphs

DOI10.1109/81.414831MaRDI QIDQ4868153zbMATH OpenOpenAlexFDO

Authors Chong S. Rim, Kazuo Nakajima

Publication date 5 March 1996

Published in IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/81.414831

zbMATH Keywords

NP-completenessvertex coloring problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• A note on maximum independent sets in rectangle intersection graphs
• scientific article; zbMATH DE number 4142090
• scientific article; zbMATH DE number 867674
• Minimum vertex cover in rectangle graphs

Cited in

(13)

• A note on maximum independent sets in rectangle intersection graphs
• Maximum independent set and maximum clique algorithms for overlap graphs
• Interval graph limits
• Dominating set on overlap graphs of rectangles intersecting a line
• Independent set of intersection graphs of convex objects in 2D
• On some applications of the selective graph coloring problem
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• Placing Text Boxes on Graphs
• Matching colored points with rectangles
• On rectangle intersection graphs with stab number at most two
• On rectangle intersection graphs with stab number at most two
• Maximum bipartite subgraphs of geometric intersection graphs
• A characterization of intersection graphs of the maximal rectangles of a polyomino

This page was built for publication: On rectangle intersection and overlap graphs

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