Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/1986
Type: Relatório
Title: Optimum grid representations
Author(s)/Inventor(s): Fampa, Márcia Helena Costa
Klein, S.
Protti, Fábio
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 [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.
Keywords: Interseção de grafos
Grade de interseção de grafos
Programação inteira
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Department : Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Issue: 2302
Issue Date: 31-Dec-2002
Publisher country: Brasil
Language: eng
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)
URI: http://hdl.handle.net/11422/1986
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
23_02_000613457.pdf212,76 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.