On unit grid intersection graphs and several other intersection graph classes

MaRDI QIDQ6621249zbMATH OpenFDO

Authors 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

Recommendations

• Simple Geometrical Intersection Graphs
• Geometric Intersection Graphs: Do Short Cycles Help?
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• Unit-length rectangular drawings of graphs
• Intersection graphs of segments

Cites work

• A special planar satisfiability problem and a consequence of its NP- completeness
• Ferrers dimension of grid intersection graphs
• Geometric Intersection Graphs: Do Short Cycles Help?
• Intersection graphs of pseudosegments: chordal graphs
• Intersection graphs of segments
• On grid intersection graphs
• Recognizing string graphs in NP
• Simple Geometrical Intersection Graphs
• String graphs. II: Recognizing string graphs is NP-hard
• The complexity of the partial order dimension problem: closing the gap

Cited in

(1)

• Recognizing geometric intersection graphs stabbed by a line

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

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