Rectangle-visibility representations of bipartite graphs

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 colline...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 1997-05, Vol.75 (1), p.9-25
Main Authors: Dean, Alice M., Hutchinson, Joan P.
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771
DOI:10.1016/S0166-218X(96)00029-7