Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/11422/2582
Especie: Artigo
Título : Optimal grid representations
Autor(es)/Inventor(es): Fampa, M. H. C.
Klein, S.
Protti, F.
Rêgo, D. C. A.
Resumen : A graph G is a grid intersection graph if G is the intersection graph of ℋ ∪ ℐ, where ℋ and ℐ 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 ℋ ∪ ℐ is a representation of G. As a consequence of a characterization of grid intersection graphs by Kratochvíl, we observe that when 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 × 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) ∈ N × N | 1 ≤ y ≤ r, 1 ≤ x ≤ 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 ℛ such that the sum of the lengths of the segments in ℛ is minimum. In this work we introduce this problem and present a mixed integer programming formulation to solve it.
Palabras clave : Intersection graph of segments
Grid intersection graph
Grid representation
Integer programming
Materia CNPq: CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA::TELECOMUNICACOES
Departamento: Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
Editorial : Wiley Subscription Services, Inc., A Wiley Company
En: Networks
Volumen: 44
Número: 3
Fecha de publicación: 9-ago-2004
DOI: http://dx.doi.org/10.1002/net.20032
País de edición : Estados Unidos
Idioma de publicación: eng
Tipo de acceso : Acesso Aberto
ISSN: 1097-0037
Citación : Fampa, M. H. C., Klein, S., Protti, F. and Rêgo, D. C. A. (2004), Optimal grid representations. Networks, 44 (3): 187–193.
URI : http://hdl.handle.net/11422/2582
Aparece en las colecciones: Engenharias

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
net20032.pdf212,76 kBAdobe PDFVisualizar/Abrir


Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.