Characterizations of special classes of contact B0-VPG graphs.

FLAVIA BONOMO; MARÍA PÍA MAZZOLENI; MARIANO LEONARDO REAN; BERNARD RIES

Buenos Aires

Congreso; LXVI Reunión Anual de Comunicaciones Científicas. 2017; 2017

Golumbic et al. introduced the concept of vertex intersection graphs ofpaths in a grid (referred to as VPG graphs). An undirected graph G = (V;E)is called a VPG graph if one can associate a path in a rectangular grid witheach vertex such that two vertices are adjacent if and only if the correspondingpaths intersect on at least one grid-point.A particular attention was paid to the case where the paths have a limitednumber of bends. An undirected graph G = (V;E) is then called a Bk-VPGgraph, for some integer k 0, if one can associate a path with at most k bendsin a rectangular grid with each vertex such that two vertices are adjacent ifand only if the corresponding paths intersect on at least one grid-point.A graph G is a B0-VPG graph if it is the vertex intersection graph ofhorizontal and vertical paths in a grid. In this work, we are interested ina subclass of B0-VPG graphs called contact B0-VPG. An undirected graphG = (V;E) is said to be contact B0-VPG if one can associate a horizontal orvertical path in a rectangular grid with each vertex, such that two vertices areadjacent if and only if the corresponding paths intersect on at least one grid-point without crossing each other and without sharing an edge of the grid. Wepresent a minimal forbidden induced subgraph characterization of contact B0-VPG graphs within some special graph classes. More specically, we considertree-cographs, P4-tidy graphs, (1; 2)-polar graphs and chordal graphs, and wecharacterize those graphs from these families that are contact B0-VPG.