  This paper is concerned with the recognition of approximate graph products
with respect to the Cartesian product. Most graphs are prime, although they can
have a rich product-like structure. The proposed algorithms are based on a
local approach that covers a graph by small subgraphs, so-called partial star
products, and then utilizes this information to derive the global factors and
an embedding of the graph under investigation into Cartesian product graphs.
