**F. Aurenhammer, J. Hagauer, and W. Imrich**

Let be a connected graph with vertices and edges. We develop an
algorithm that finds the prime factors of with respect to Cartesian
multiplication in time and space. This shows that
factoring is at most as costly as sorting its edges. The algorithm gains
its efficiency and practicality from using only basic properties of product
graphs and simple data structures.