Responsables : Alain Hertz (alain.hertz@gerad.ca)

Comité organisateur : GERAD

Conférencier invité : Elad Cohen (étudiant au doctorat, University of Haifa, Israel)

Résumé :
We investigate the class of vertex intersection graphs of paths on a grid, and specifically consider the subclasses that are obtained when each path in the representation has at most k bends (turns). We call such a subclass the Bk-VPG graphs, k>=0. The motivation for this study comes from the world of chip manufacturing, where circuit layout is modeled as paths (wires) on a grid, where it is natural to constrain the number of bends per wire for reasons of feasibility and to reduce the cost of the chip.
We present a complete hierarchy of VPG graphs relating them to other known families of graphs. String graphs are equivalent to VPG graphs. The grid intersection graphs are shown to be equivalent to the bipartite B0-VPG graphs.
Chordal B0-VPG graphs are shown to be exactly Strongly Chordal B0-VPG graphs. We prove the strict containment of B0-VPG and circle graphs into B1-VPG. Planar graphs are known to be in the class of string graphs, and we prove here that planar graphs are B3-VPG graphs.
In the case of B0-VPG graphs, we observe that a set of horizontal and vertical segments have strong Helly number 2. We show that the coloring problem for Bk-VPG graphs, for k>=0, is NP-complete and give a 2-approximation algorithm for coloring B0-VPG graphs. Furthermore, we prove that triangle-free B0-VPG graphs are 4-colorable, and this is best possible.
This is joint work with Andrei Asinowski, Martin Charles Golumbic, Vincent Limouzy, Marina Lipshteyn, and Michal Stern.

Adresse du site web de l'événement : http://www.gerad.ca/fr/activites/seminaire.php?id=832

Courriel à contacter, si les gens ont des questions : valerie.lavoie-leblanc@gerad.ca

Adresse du lieu où se déroule l'événement :

Salle 6516, Pavillon André-Aisenstadt, Campus de l'Université de Montréal, 2920, chemin de la Tour