Please use this identifier to cite or link to this item:
|Title:||Optimum grid representations|
|Author(s)/Inventor(s):||Fampa, Márcia Helena Costa|
Rêgo, D. C. A.
|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 , 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.|
|Keywords:||Interseção de grafos|
Grade de interseção de grafos
|Subject CNPq:||CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO|
|Production unit:||Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais|
|In:||Relatório Técnico NCE|
|Right access:||Acesso Aberto|
|Citation:||FAMPA,M. H. C. et al. Optimum grid representations. Rio de Janeiro: NCE, UFRJ, 2002. 12 p. (Relatório Técnico, 23/02)|
|Appears in Collections:||Relatórios Técnicos e de Pesquisa|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.