Is there an algorithm to determine whether a given simple graph $G$ is a product graph, typically, say a cartesian product graph of two smaller simple graphs $G\_1, G\_2$, such that the two simple graphs have the cartesian product of their vertex sets having the same cardinality of the graph $G$, that is, $V(G\_1)\times V(G\_2)=V(G)$?


Since every graph could be written as a cartesian product of some graphs(though some might be degenerate), I think it would be possible to determine whether a graph is the product (any graph product) of two simpler graphs in a nice way.



Recognition of a graph as a product of its quotients
The best algorithm is linear in the number of edges:see [Imrich, Wilfried; Peterin, Iztok (2007), "Recognizing Cartesian products in linear time", Discrete Mathematics 307 (3-5): 472–483](https://www.sciencedirect.com/science/article/pii/S0012365X06005280).


An easy-to-understand algorithm can be found [here](http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_decompositions/graph_products.html), which is basically keeping a set of edges that necessarily come from the same factor of the product graph. If all edges are necessarily from the same factor, the graph is not a nontrivial product. Otherwise there exists a decomposition.


