Treewidth and logical definability of graph products

In this paper we describe an algorithm that, given a tree-decomposition of a graph G and a tree-decomposition of a graph H, provides a tree-decomposition of the cartesian product of G and H. Using this algorithm, we derive upper bounds on the treewidth (resp. on the pathwidth) of the cartesian product of two graphs, expressed in terms of the treewidth (resp. pathwidth) and the size of the factor graphs. In the context of graph grammars and graph logic, we prove that the cartesian product of a class of graphs by a finite set of graphs preserves the property of being a context-free set, and that the cartesian product by a finite set of connected graphs preserves MS1-definability and MS2-definability. We also prove that the cartesian product of two MS2-definable classes of connected graphs is MS2-definable.