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

On Intersection Graphs of Paths in a Grid

Bernard Ries LAMSADE, Université Paris Dauphine, France

Golumbic et al. recently defined the so-called EPG graphs and VPG graphs: EPG graphs are Edge intersection graphs of Paths in a Grid and VPG graphs are Vertex intersection graphs of Paths in a Grid. We investigate the subclasses in which we limit the number of bends per path: 1 for EPG graphs which gives us the \(B_1\)-EPG graphs; 0 for VPG graphs which gives us the \(B_0\)-VPG graphs. In chip manufacturing, a 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 some characterization of subclasses of chordal graphs which are \(B_1\)-EPG resp. \(B_0\)-VPG graphs.

This is joint work with M. Golumbic and A. Asinowski.