Factoring a graph in polynomial time (Q579285)

The Cartesian product \(G\times H\) of graphs G and H has vertices (g,h) where g is a vertex in G and h a vertex in H. Two vertices of \(G\times H\), say \((g_ 1,h_ 1)\) and \((g_ 2,h_ 2)\), are connected by an edge in \(G\times H\), just when either \(\{g_ 1,g_ 2\}\) is an edge of G and \(h_ 1=h_ 2\), or when \(g_ 1=g_ 2\) and \(\{h_ 1,h_ 2\}\) is an edge of H. It was proved by \textit{G. Sabidussi} [Math. Z. 72, 446-457 (1960; Zbl 0093.376)] that Cartesian product admits unique factorization. The author proves that there is a polynomial time algorithm for constructing the prime factorization of a given connected graph. The same result, using completely different techniques, was proved also in [\textit{J. Feigenbaum, J. Hershberger} and \textit{A. A. Schaffer}, Discrete Appl. Math. 12, 123-138 (1985; Zbl 0579.68028)].