ABSTRACT
In Chapter 15, we proved the unique prime factorization property of connected graphs with respect to the Cartesian product. The proof did not provide us with a fast, or at least polynomial, algorithm to find the factorization. Here we exploit the close relationship between the relation Θ and the Cartesian product to prove a structure theorem that has both the unique prime factorization property of connected graphs and a polynomial factorization algorithm as immediate consequences.
