Sesión Matemática Discreta

Diciembre 13, 11:40 ~ 12:00

Characterizations of special classes of contact B 0 -VPG graphs

Rean, Mariano

Golumbic et al. introduced in \cite{asinowski} the concept of \textit{vertex intersection graphs of paths in a grid} (referred to as \textit{VPG graphs}). An undirected graph $G=(V,E)$ is called a VPG graph if one can associate a path in a rectangular grid with each vertex such that two vertices are adjacent if and only if the corresponding paths intersect on at least one grid-point. %VPG graphs are related to another family of intersection graphs, namely \textit{string graphs}. A string graph is a graph in which every vertex corresponds to a curve in the plane and two vertices are adjacent if and only if the corresponding curves intersect. Thus, it is easy to see that VPG graphs and string graphs are equivalent. A particular attention was paid to the case where the paths have a limited number of bends. An undirected graph $G=(V,E)$ is then called a \textit{$B_k$-VPG graph}, for some integer $k\geq 0$, if one can associate a path with at most $k$ bends in a rectangular grid with each vertex such that two vertices are adjacent if and only if the corresponding paths intersect on at least one grid-point. %The class of $B_0$-VPG graphs form a subclass of the well-known \textit{segment graphs}. Indeed, the class of \textit{$k$-DIR graphs} has been defined as the class of segment graphs in which the straight-line segments lie in at most $k$ directions. Therefore, it is easy to see that $B_0$-VPG graphs are equivalent to $2$-DIR graphs. In this paper, we are interested in a subclass of $B_0$-VPG graphs called \textit{contact $B_0$-VPG}. An undirected graph $G=(V,E)$ is said to be contact $B_0$-VPG if one can associate a horizontal or vertical path in a rectangular grid with each vertex, such that two vertices are adjacent 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. %In other words, whenever two vertices are adjacent, the corresponding paths intersect on an endpoint of one of the paths. We will consider some special graph classes, namely tree-cographs, $P_4$-tidy graphs, $(1,2)$-polar graphs and chordal graphs, and we will characterize those graphs from these families that are contact $B_0$-VPG. \begin{thebibliography}{1} \bibitem{asinowski} {Asinowski}, A., E.~{Cohen}, M.~{Golumbic}, V.~{Limouzy}, M.~{Lipshteyn} and M.~{Stern}, \emph{Vertex intersection graphs of paths on a grid}, Journal of Graph Algorithms and Applications \textbf{16} (2012), pp.~129--150. \end{thebibliography}

Autores: Rean, Mariano / Bonomo, Flavia / Mazzoleni, Maria Pia / Ries, Bernard.