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)$][1], 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. 

 

  [1]: http://www.math.u-bordeaux1.fr/~jcouveig/publi/CaCou.pdf