A polynomial time algorithm for finding the prime factors of cartesian-product graphs

We consider the computational complexity of recognizinf concerned cartesian product graphs. Sabidussi gives a non-algorithmic proof that the cartesian factorization is unique. He uses a tower of successively coarser equivalence relations on the edge set in which each prime factor of the graph is identified with an equivalence class in the coarsest of the relations. We first explore the structure and size of the relation at the base of the tower. Then we give a polynomial-time algorithm to compute the relations and to construct the prime factors of any connected graph. The bounds on the size of the relations are crucial to the runtime analysis of our algorithm.