Rectangle-Visibility Representations of Bipartite Graphs (Extended Abstract)

Dean, Alice M. and Hutchinson, Joan P. (1995) Rectangle-Visibility Representations of Bipartite Graphs (Extended Abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 159-166(Official URL: http://dx.doi.org/10.1007/3-540-58950-3_367).

Full text not available from this repository.

Abstract

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 \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 rectangle-visibility graph if and only if p \leq 4. Finally, it is shown that every bipartite rectangle-visibility graph on n \geq 4 vertices has at most 4n - 12 edges.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-58950-3_367
Classifications: Z Theory > Z.500 Representations
P Styles > P.900 Visibility
URI: http://gdea.informatik.uni-koeln.de/id/eprint/144

Actions (login required)

View Item View Item