Optimum grid representations

Abstract

A graph G is a grid intersection graph if G is the intersection graph of H U I, where H and I are, respectively, finite families of horizontal and vertical linear segments in the plane such that do two parallel segments intersect. (This definition implies that every grid intersection graph is bipartite.) Any family of segments realizing G is a representation of G. As a consequence of a characterization of grid intersection graphs by Kratochvíl [7], we observe that a bipartite graph G = (U ᵁ 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, where r = |U| and s = |W|. A natural problem, with potential applications to circuit layout, is the following: among all the possible representations of G on the (r x s)-grid, find a representation R such that the sum of the lenghts of the segments in R is minimum. In this work we introduce this problem and present a mixed integer programming formulation to solve it.