Rectangle-visibility representations of bipartite graphs (Q1363757)

This paper considers rectangle-visibility graphs, where adjacencies among rectangles in the plane are determined by horizontal and vertical visibility. Such graphs have application to VLSI design and have been considered in connection with circuit board design. Those complete bipartite graphs that can be so represented in general and when rectangles are not allowed to have collinear sides have been characterized. An upper bound on the number of edges of any bipartite rectangle-visibility graph has also been derived.