RectangleVisibility Representations of Bipartite Graphs (Extended Abstract)Dean, Alice M. and Hutchinson, Joan P. (1995) RectangleVisibility Representations of Bipartite Graphs (Extended Abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 159166(Official URL: http://dx.doi.org/10.1007/3540589503_367). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540589503_367
AbstractThe paper considers representations of bipartite graphs as rectanglevisibility 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 \leq p, K_{p,q} has a representation with no rectangles having collinear sides if and only if p < 3 or p = 3 and q \leq 4. More generally, it is shown that K_{p,q} is a rectanglevisibility graph if and only if p \leq 4. Finally, it is shown that every bipartite rectanglevisibility graph on n \geq 4 vertices has at most 4n  12 edges.
Actions (login required)
