Ferrers dimension of grid intersection graphs

DOI10.1016/j.dam.2015.05.035zbMath1350.05142OpenAlexW650364680MaRDI QIDQ344841

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

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)

Related Items

Sublinear approximation algorithms for boxicity and related problems ⋮ Stick graphs with length constraints ⋮ Recognizing Stick Graphs with and without Length Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Permutation bigraphs and interval containments
• On orthogonal ray graphs
• Two remarks on circular arc graphs
• Grid intersection graphs and boxicity
• Cubicity, boxicity, and vertex cover
• Bipartite permutation graphs
• On dimensional properties of graphs
• On the Ferrers dimension of a digraph
• On grid intersection graphs
• Dimension of the crown \(S^k_n\)
• A special planar satisfiability problem and a consequence of its NP- completeness
• Intersection dimensions of graph classes
• Efficient graph representations
• Permuting matrices to avoid forbidden submatrices
• Representing digraphs using intervals or circular arcs
• List homomorphisms and circular arc graphs
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• Approximation of Minimum Cost Homomorphisms
• Graph Classes: A Survey
• Interval bigraphs and circular arc graphs
• Boxicity and Poset Dimension