In practice, graphs often occur as perturbed product structures, so-called approximate graph products. The practical application of the well-known prime factorization algorithms is therefore limited, since most graphs are prime, although they can have a product-like structure. This work is concerned with the strong graph product. Since strong product graphs G contain subgraphs that are itself products of subgraphs of the underlying factors of G, we follow the idea to develop local approaches that cover a graph by factorizable patches and then use this information to derive the global factors. First, we investigate the local structure of strong product graphs and introduce the backbone B(G) of a graph G and the so-called S1-condition. Both concepts play a central role for determining the prime factors of a strong product graph in a unique way. Then, we discuss several graph classes, in detail, NICE, CHIC and locally unrefined graphs. For each class we construct local, quasi-linear time prime factorization algorithms. Combining these results, we then derive a new local prime factorization algorithm for all graphs. Finally, we discuss approximate graph products. We use the new local factorization algorithm to derive a method for the recognition of approximate graph products. Furthermore, we evaluate the performance of this algorithm on a sample of approximate graph products.

In practice, graphs often occur as perturbed product structures, so-called approximate graph products. The practical application of the well-known prime factorization algorithms is therefore limited, since most graphs are prime, although they can have a product-like structure. This work is concerned with the strong graph product. Since strong product graphs G contain subgraphs that are itself products of subgraphs of the underlying factors of G, we follow the idea to develop local approaches that cover a graph by factorizable patches and then use this information to derive the global factors. First, we investigate the local structure of strong product graphs and introduce the backbone B(G) of a graph G and the so-called S1-condition. Both concepts play a central role for determining the prime factors of a strong product graph in a unique way. Then, we discuss several graph classes, in detail, NICE, CHIC and locally unrefined graphs. For each class we construct local, quasi-linear time prime factorization algorithms. Combining these results, we then derive a new local prime factorization algorithm for all graphs. Finally, we discuss approximate graph products. We use the new local factorization algorithm to derive a method for the recognition of approximate graph products. Furthermore, we evaluate the performance of this algorithm on a sample of approximate graph products.