Groupe d’études et de recherche en analyse des décisions

Vertex Intersection Graphs of Paths on a Grid

Elad Cohen University of Haifa, Israël

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 \(B_k\)-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 \(B_0\)-VPG graphs. Chordal \(B_0\)-VPG graphs are shown to be exactly Strongly Chordal \(B_0\)-VPG graphs. We prove the strict containment of \(B_0\)-VPG and circle graphs into \(B_1\)-VPG. Planar graphs are known to be in the class of string graphs, and we prove here that planar graphs are \(B_3\)-VPG graphs. In the case of \(B_0\)-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 \(B_0\)-VPG graphs. Furthermore, we prove that triangle-free \(B_0\)-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.