| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4949887 | Discrete Applied Mathematics | 2017 | 6 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Steven Chaplick, Pavol Hell, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara,