Optimal grid representations
A graph G is a grid intersection graph if G is the intersection graph of H boolean OR I where H and I are, respectively, finite families of horizontal and vertical linear segments in the plane such that no two parallel segments intersect. (This definition implies that every grid intersection graph is bipartite.) The family H boolean OR I is a representation of G. As a consequence of a characterization of grid intersection graphs by Kratochvil, we observe that when a bipartite graph G = (U boolean OR W, E) with minimum degree at least two is a grid intersection graph, then there exists a normalized representation of G on the (r x s)-grid for r = \U\ and s = \W\, that is, a representation in which all end points of segments have integer-valued coordinates belonging to {(x, y) is an element of N x N \ 1 less than or equal to y less than or equal to r, 1 less than or equal to x less than or equal to s} and the representative segment of each vertex lies on a distinct horizontal or vertical line. A natural problem, with potential applications to circuit layout, is the following: among all the possible normalized representations of G, find a representation A such that the sum of the lengths of the segments in R is minimum. In this work we introduce this problem and present a mixed integer programming formulation to solve it. (C) 2004 Wiley Periodicals, Inc.
grid representation grid intersection graph integer programming intersection graph of segments