Ferrers dimension of grid intersection graphs

DOI10.1016/J.DAM.2015.05.035MaRDI QIDQ344841zbMATH OpenOpenAlexFDO

Authors Steven Chaplick, Pavol Hell, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara

Publication date 24 November 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.05.035

zbMATH Keywords

boxicityFerrers dimensionsegment-ray graphunit grid intersection graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph theory (05C99)

Recommendations

• Grid intersection graphs and order dimension
• Intersection dimension of bipartite graphs
• Forbidden subgraphs of bigraphs of Ferrers dimension 2
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• Grid intersection graphs and boxicity

Cites work

• scientific article; zbMATH DE number 1472165 (Why is no real title available?)
• A special planar satisfiability problem and a consequence of its NP- completeness
• Approximation of minimum cost homomorphisms
• Bipartite permutation graphs
• Cubicity, boxicity, and vertex cover
• Dimension of the crown \(S^k_n\)
• Efficient graph representations
• Graph Classes: A Survey
• Grid intersection graphs and boxicity
• Intersection dimensions of graph classes
• Interval bigraphs and circular arc graphs
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• List homomorphisms and circular arc graphs
• On dimensional properties of graphs
• On grid intersection graphs
• On orthogonal ray graphs
• On the Ferrers dimension of a digraph
• Permutation bigraphs and interval containments
• Permuting matrices to avoid forbidden submatrices
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• Representing digraphs using intervals or circular arcs
• Two remarks on circular arc graphs

Cited in

(8)

• On unit grid intersection graphs and several other intersection graph classes
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• Sublinear approximation algorithms for boxicity and related problems
• Forbidden subgraphs of bigraphs of Ferrers dimension 2
• Recognizing stick graphs with and without length constraints
• Grid intersection graphs and order dimension
• Stick graphs with length constraints
• Intersection dimension of bipartite graphs

This page was built for publication: Ferrers dimension of grid intersection graphs

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