On Intersection Graphs of Paths in a Grid
Presented by Dr. Bernard RIES
Type: Oral presentation
Track: Algorithmic Graph Theory
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. 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.