MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 typos corrected, some info added, some clean-up; added 20 characters in body
with polynomials $F,R,S,T$ F,G,R,S$ over the same field and

This

In particular, it follows that if one cannot write $f,g$ in such a way with nontrivial (that is degree at least 2) $F$ and $G$ then the original polynomial is irreducible [except if one of $f,g$ is constant, but this should not be the case in view of the question]. (I am not sure how to check this most efficiently, but if the polynomials are not too complex, just starting from maximal terms and inferring conditions on the rank and then working ones way down could be a viable, though likely not optimal, strategy.)

If one wishes to have more complete information one is now raises faced with the question when a polynomial $$F(u)-G(v)$$ is reducible(ir)reducible.

Various interesting results on this problem where obtained (see below for some recent of them), but if one wishes to have an answer for specific polynomials one migt get by via using not these results, but general irreducibilty criteria for polynomials in two variables or easier to apply criteria for this polynomial.

For the former the question pointed out in a comment by Camilo Sarmiento seems like a good resource (I reproduce the link for simplicity http://mathoverflow.net/questions/14076/irreducibility-of-polynomials-in-two-variables ).

For example the Ehrenfeucht criterion mentioned there might allow to directly exclude further cases. Also the Eisenstein (like) criteria could be quite useful. Also the paper by Davenport, Lewis, Schinzel mentioned in my comment below should contain some test, but as I have no access to the paper I do not know what exactly.

Now for more recent results specifically on this problem:

In particular, Pierrette Cassou-Noguès and Jean-Marc Coveignes (Factorisations explicites de $g(y)-h(z)$, Acta Arith. 87 (1999)) based on earlier work by Fried and Feit and others established an explict finite set of pairs of polynomials such that any pair $(F,G)$, with $F,G$ indecomposable and not linearly related (this means $F(x)$ is not of the form $AG(ax+b)+B$ with constants $A,a,B,b$ and $A,a$ non-zero, to avoid corner cases), with $F(u)-G(v)$ reducible is weakly linearly realted (I skip the def, but similar to lin related) to one of themin a simple way.

show/hide this revision's text 1

There has been a lot of work on establishing when polynomials of the form $$f(x_1, \dots, x_r) - g(y_1, \dots, y_s)$$ are reducible (over the complex numbers, but also over other fields). (Negating them, or special cases thereof would thus yield criteria, in the sense of conditions, when such a polynomial is irreducible.)

To a considerable extent one can reduce this problem to the case $r=s=1$. Namely, Davenport and Schinzel (Two Problems Concerning Polynomials, J. reine angew. Math., 1964) proved (this is Theorem 2, up to signchange to match the question, of the paper.

The polynomial, over a field of charateristic $0$, $$f(x_1, \dots, x_r) - g(y_1, \dots, y_s)$$ is reducible if and only if $f(x_1, \dots, x_r) = F(R(x_1, \dots, x_r))$ and $g(y_1, \dots, y_s) = G(S(y_1, \dots, y_s))$ with polynomials $F,R,S,T$ over the same field and $$F(u) - G(v)$$ is reducible over the same field.

Note that the main case the authors care about is indeed the complex one.

This now raises the question when a polynomial $$F(u)-G(v)$$ is reducible.

Under the assumption that the $F$ and $G$ are indepecomposable (indepcomposable meaning the polynomial is not the composition of two polynomials) there is a complete answer know (over the complex numbers).

In particular, Pierrette Cassou-Noguès and Jean-Marc Coveignes (Factorisations explicites de $g(y)-h(z)$, Acta Arith. 87 (1999)) based on earlier work by Fried and Feit and others established an explict finite set of pairs of polynomials such that any pair $(F,G)$, with $F,G$ indecomposable and not linearly related (this means $F(x)$ is not of the form $AG(ax+b)+B$ with constants $A,a,B,b$ and $A,a$ non-zero, to avoid corner cases), with $F(u)-G(v)$ reducible is weakly linearly realted (I skip the def, but similar to lin related) to one of them in a simple way.

This sets is too large to give here (yet the paper is linked anyway) but what can be said briefly (and was already known before) is that the degrees of both polynomials are equal, and equal to one of $7, 11, 13, 15, 21, 31$.

Note that this result uses the Classification of Finite Simple Groups.

There are also other results related to this. For example Yuri Bilu (Acta Arith. 90 (1999)) studied when $F(u)-G(v)$ has a factor of degree at most two (where there is no assumption of indecomposability). Roughly, there can essentially only be a quadratic factor if both are Chebyshev polynolmials of degree a power of two.