Cartesian graph factorization at logarithmic cost per edge

Let G be a connected graph with n vertices and m edges. We develop an algorithm that finds the (unique) prime factors of G with respect to the Cartesian product in O(m log n) time and O(m) space. This shows that factoring G 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.