Recognizing triangulated Cartesian graph products

Computational meshes for numerical simulation frequently show—at least locally—a structure resembling a triangulated grid. Our goal is to recognize product-like structures in triangular meshes. We define triangulated Cartesian products of graphs and analyze their structural properties. We show how to recognize and factorize graphs that are triangulated products of two factors, when the factors are triangle-free graphs. We also discuss properties of products with more than two factors.