On grid intersection graphs (Q1174140): Difference between revisions

A bipartite graph \(G\) with vertex bipartition \(X\) and \(Y\) has a grid representation if \(X\) and \(Y\) correspond to sets of horizontal and vertical segments in the plane, respectively, such that \(G\) is the intersection graph of these segments, i.e. vertices of \(G\) are adjacent whenever the corresponding segments have nonempty intersection. It is shown that every planar bipartite graph has some grid representation. On the other hand, certain infinite families of bipartite graphs are presented, that have no grid representations --- including the point line incidence graphs of projective planes.