Abstract | ||
---|---|---|
We investigate the Ferrers dimension of classes of grid intersection graphs and show properties and characterizations. In particular, we show that (1) the grid intersection graphs form a proper subclass of the class of bipartite graphs of Ferrers dimension 4, (2) segment-ray graphs have a forbidden submatrix characterization, and (3) a bipartite graph is a unit grid intersection graph if and only if it is the intersection of two bipartite permutation graphs. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1016/j.dam.2015.05.035 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Ferrers dimension,Boxicity,Segment-ray graph,Unit grid intersection graph | Permutation graph,Discrete mathematics,Block graph,Combinatorics,Indifference graph,Chordal graph,Intersection graph,Pathwidth,1-planar graph,Mathematics,Trapezoid graph | Journal |
Volume | ISSN | Citations |
216 | 0166-218X | 1 |
PageRank | References | Authors |
0.36 | 21 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
steven chaplick | 1 | 76 | 16.91 |
Pavol Hell | 2 | 2638 | 288.75 |
Yota Otachi | 3 | 161 | 37.16 |
Toshiki Saitoh | 4 | 87 | 14.95 |
Ryuhei Uehara | 5 | 528 | 75.38 |