Please use this identifier to cite or link to this item:

`http://hdl.handle.net/11422/2582`

Type: | Artigo |

Title: | Optimal grid representations |

Author(s)/Inventor(s): | Fampa, M. H. C. Klein, S. Protti, F. Rêgo, D. C. A. |

Abstract: | 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. |

Keywords: | Intersection graph of segments Grid intersection graph Grid representation Integer programming |

Subject CNPq: | CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA::TELECOMUNICACOES |

Production unit: | Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais |

Publisher: | Wiley Subscription Services, Inc., A Wiley Company |

In: | Networks |

Volume: | 44 |

Issue: | 3 |

Issue Date: | 9-Aug-2004 |

DOI: | 10.1002/net.20032 |

Publisher country: | Estados Unidos |

Language: | eng |

Right access: | Acesso Aberto |

ISSN: | 1097-0037 |

Citation: | Fampa, M. H. C., Klein, S., Protti, F. and Rêgo, D. C. A. (2004), Optimal grid representations. Networks, 44 (3): 187–193. |

Appears in Collections: | Engenharias |

Files in This Item:

File | Description | Size | Format | |
---|---|---|---|---|

net20032.pdf | 212.76 kB | Adobe PDF | View/Open |

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