On unit grid intersection graphs and several other intersection graph classes

MaRDI QIDQ6621249

Irina Mustaţă, Martin Pergel

Publication date: 18 October 2024

Published in: Acta Mathematica Universitatis Comenianae. New Series (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Ferrers dimension of grid intersection graphs
• String graphs. II: Recognizing string graphs is NP-hard
• On grid intersection graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• Intersection graphs of segments
• The Complexity of the Partial Order Dimension Problem: Closing the Gap
• Intersection Graphs of Pseudosegments: Chordal Graphs
• Geometric Intersection Graphs: Do Short Cycles Help?
• Simple Geometrical Intersection Graphs
• Recognizing string graphs in NP

This page was built for publication: On unit grid intersection graphs and several other intersection graph classes