About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Abstract
A bipartite graph G = (X, Y; E) has a grid representation if X and Y correspond to sets of horizontal and vertical segments in the plane, respectively, such that (xi, yj) ∈ E if and only if segments xi and yj intersect. We prove that all planar bipartite graphs have a grid representation, and exhibit some infinite families of graphs with no grid representation-among them the point line incidence graph of projective planes. © 1991.