Publication
Discrete Mathematics
Paper

On grid intersection graphs

View publication

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.

Date

Publication

Discrete Mathematics

Authors

Share