REPRESENT-VISIBILITY REPRESENTATIONS OF BIPARTITE GRAPHS

The paper considers representations of bipartite graphs as rectangle-v isibility graphs, i.e., graphs whose vertices are rectangles in the pl ane, with adjacency determined by horizontal and vertical visibility. It is shown that, for p less than or equal to q, K-p,K-q has a represe ntation with no rectangles having collinear sides if and only if p les s than or equal to 2 or p = 3 and q less than or equal to 4. More gene rally, it is shown that K-p,K-q is a rectangle-visibility graph if and only if p less than or equal to 4. Finally, it is shown that every bi partite rectangle-visibility graph on n greater than or equal to 4 ver tices has at most 4n - 12 edges.