| Popis: |
The paper considers representations of bipartite graphs as rectangle-visibility graphs , i.e., graphs whose vertices are rectangles in the plane, with adjacency determined by horizontal and vertical visibility. It is shown that, for p ⩽ q , K p , q has a representation with no rectangles having collinear sides if and only if p ⩽ 2 or p = 3 and q ⩽ 4. More generally, it is shown that K p , q is a rectangle-visibility graph if and only if p ⩽ 4. Finally, it is shown that every bipartite rectangle-visibility graph on n ⩾ 4 vertices has at most 4 n − 12 edges. |
Full Text from ScienceDirect