Complexity of "is a graph a product" This question arises out of pure curiosity (it came up while thinking about unshuffling a string, but I'm not sure if it's actually related) so I hope it's appropriate.

There are various graph products, and I'm interested in any of them here. What is the complexity of determining whether a graph $K$ is isomorphic to a non-trivial product? (Certainly for the Cartesian product, $K = K \square 1$ where $1$ is the graph with one vertex.)

I've looked at the pages "factor graph" and "graph factorization" on Wikipedia, but neither seem to be related. Is this problem known under another name?
Check the paper Wilfried, Imrich; Iztok, Peterin, Recognizing Cartesian products in linear time. Discrete Math., 307, 3-5, Page(s): 472--483, 2007. I think that Imrich has more papers for other products.