Irreducibility of polynomials in two variables Let $k$ be a field. I am interested in sufficient criteria for $f \in k[x,y]$ to be irreducible. An example is Theorem A of this paper (Brindza and Pintér, On the irreducibility of some polynomials in two variables, Acta Arith. 1997).
Does anyone know of similar results in the same vein? How about criteria over fields other than the complex numbers?  
 A: A trick which works surprisingly often in my experience: If the Newton polytope of $f$ can not be written as a Minkowski sum of two smaller polytopes, then $f$ is irreducible. I think of this as a generalization of Eisenstein's criterion. 
It is surprisingly easy to test whether a lattice polygon in $\mathbb{R}^2$ can be written as a Minkowski sum of smaller lattice polygon. Let $P$ be a lattice polytope. Travel around $\partial P$ and write down the vectors pointing from each lattice point to the next lattice point; call this sequence of vectors $v(P)$. For example, if our polynomial is $a y^2 + b y + c xy + d + e x + f x^2 + g x^3$, with $adg \neq 0$, then the lattice points on the boundary are $(0,2)$, $(0,1)$, $(0,0)$, $(1,0)$, $(2,0)$, $(3,0)$ so $v(P) =(\ (0,-1),\ (0,-1),\ (1,0),\ (1,0),\ (1,0),\ (-3,2)\ )$. (Note that $(1,1)$ is not on the boundary of the triangle.)
It turns out that $v(A + B)$ is simply the sequences $v(A)$ and $v(B)$, interleaved by sorting their slopes .  So, if $P$ can be written as the Minkowski sum $A+B$, we must be able to partition $v(P)$ into two disjoint sub-sequences, each of which sums to zero. In the above example, this can't be done, so any polynomial of the form $a y^2 + b y + c xy + d + e x + f x^2 + g x^3$, with $adg \neq 0$ is irreducible. 
As an example of a polynomial which could factor, look at $a y^2 + by + c xy + dx + e x^2$. So the boundary is $(0,2)$, $(0,1)$, $(1,0)$, $(2,0)$, $(1,1)$ with $v(P) = (\ (0,-1),\ (1,-1),\ (1,0),\ (-1,1),\ (-1, 1)\ )$. This is the interleaving of $(\ (0,-1),\  (1,0),\  (-1, 1)\ )$ and $(\ (1,-1),\ (-1,1)\ )$, so a polynomial with this Newton polytope could factor.
A: One of my all-time leading candidates for Most Preposterous Theorem Ever:
Definition: A polynomial $f(x) \in \mathbb{C}[x]$ is indecomposable if whenever $f(x) = g(h(x))$ for polynomials $g$, $h$, one of $g$ or $h$ is linear.
Theorem. Let $f, g$, be nonconstant indecomposable polynomials over $\mathbb C$. Suppose that $f(x)-g(y)$ factors in $\mathbb{C}[x,y]$. Then either $g(x) = f(ax+b)$ for some $a,b \in \mathbb{C}$, or
$$\operatorname{deg} f = \operatorname{deg} g = 7, 11, 13, 15, 21, \text{ or } 31,$$
and each of these possibilities does occur.
The proof uses the classification of the finite simple groups [!!!] and is due to Fried [1980, in the proceedings of the 1979 Santa Cruz conference on finite groups], following a the reduction of the problem to a group/Galois-theoretic statement by Cassels [1970]. [W. Feit, "Some consequences of the classification of finite simple groups," 1980.]
A: there is a theorem of Ruppert, but I don't know it is useful or not. You can try: 
pdf - arXiv:math/9808021v1 [math.NT] 5 Aug 1998
A: What follows is more a series of considerations than a practical algorithm, but could still be of interest. The main idea is that it's easier to work with one-variable polynoms, so we trade a bad problem in two variables for several bad problems in one variable.
The key point is the following lemma (assume $k$ is of characteristic zero!): if $P(X,Y)$ is a two-variable polynom and there are enough distinct values of $a$ such that $P(X,a)$ is a constant polynomial, then $P(X,Y)$ is a polynom in $Y$ only. The proof is by arguing that $P(X,a)$ being a constant polynom means that $a$ is a root for the polynom (in $Y$) coefficient of $X^n$ for all $n>0$. And that can't happen too often in characteristic zero, unless those coefficients are zero polynoms, hence $P(X,Y)$ is reduced to its constant term as a polynom in $X$, hence is only a polynom in $Y$, as was to be proved.
Now, for your question : if you suppose a $P(X,Y)$ isn't irreducible, say factors as $Q(X,Y)R(X,Y)$, but many $P(X,a)$ are irreductible, then that means for each such $a$ either $Q(X,a)$ or $R(X,a)$ is a constant, hence given enough of those $a$, one of $Q$ or $R$ at least is only a polynom in $Y$ by the lemma, say $R$.
Then if you manage to fully factor $P(a,Y)=Q(a,Y)R(Y)$ for some $a$ (again dropping to a one-variable polynom), you get a list with $R$  (and divisors of $R$): check each element for divisibility of $P(X,Y)$. If none is good, $P$ is irreducible.
EDIT:


*

*In fact, after you have found $R$ is a polynom in $Y$, just consider the gcd of the coefficients of the $X^n$ -- if you get $1$, $P$ is irreducible.

*The previous considerations mostly prove that a cheating polynom (ie: not irreducible although it appears to be when evaluated along a variable) necessarily has a very precise form, which makes it susceptible to easy factorisation.

A: If $k$ is algebraically closed, then any two components of the projective closure of $\text{Spec } k[x, y]/(f(x, y))$ intersect by Bezout's theorem, and one can check for the existence of such points by looking at where the partial derivatives simultaneously vanish (the singular points).  For example, $f(x, y) = x^2 + 2xy + y^2 - 1$ has projective closure defined by $F(X, Y, Z) = X^2 + 2XY + Y^2 - Z^2$ and the partial derivatives vanish at $(1 : -1 : 0)$, the intersection of the components $X + Y - Z = 0$ and $X + Y + Z = 0$.
Generically, $k[x]$ is a UFD, so Eisenstein's criterion applies, although I am not sure how practical this is. 
A: Quite a useful result can be found in Schmidt's lecture notes on Equations over finite fields (Theorem III.1B in SLNM 536). Suppose that $K$ is any field and let $f(x,y)=c_0y^d+c_1(x)y^{d-1}+
\cdots+c_d(x) \in K[x,y]$, with $c_0 \neq 0$.  Let 
$$
\psi(f)=\sup_{1\leq
i\leq d}\frac{\deg c_i}{i}.
$$
Then $f$ is absolutely irreducible over $K$ provided that that $\psi(f)=m/d$ with $\gcd(m,d)=1$.
This shows, for example, that the polynomial $f(x,y)=g(x)-h(y)$ is irreducible when  $\deg g$ and $\deg h$ are coprime.
A: Let $f\in A[x][y]$ where $A$ is a UFD and assume that $f$ is monic, i.e that it can be written as
$$
f=a_0+a_1 y+\ldots a_{n-1}y^{n-1}+y^n,
$$
with $a_i\in A[x]$. Assume that there exists an irreducible polynomial $g\in A[x]$ such that
$g|a_i$ for $i=0\ldots n-1$ and $g^2\nmid a_0$ then by Eisenstein's criterion $f$ is irreducible over $A[x]$ and therefore irreducible in $A[x,y]$. I've used the fact that $A$ was a UFD only to make sure that $gA[x]$ in $A[x]$ is a prime ideal. (Of course Eisenstein criterion is a very special case which fits within the method of the Newton polygon).
Using this idea and induction it is easy to see that polynomials like
$$
(*)\;\;\;\;  x_1^{n_1}+x_2^{n_2}+\ldots x_r^{n_r}\in \mathbf{C}[x_1,x_2,\ldots x_r],
$$
are irreducible whenever $n_i\geq 1$ and $r\geq 3$, since the polynomial $x_1^{n_1}+x_2^{n_2}$
has always a multiplicity one irreducible divisor.
More generally there is the so called Ehrenfeucht criterion which says that
$$
(**) \;\;\;\; f_1(x_1)+f_2(x_2)+\ldots f_r(x_r)\in\mathbf{C}[x_1,\ldots,x_r],
$$
is always irreducible if $\deg(f_i)\geq 1$ and $r\geq 3$. In the case where $r=2$ 
it is still irreducible if one has $(\deg(f_1),\deg(f_2))=1$.
Note that the polynomials in $(\star)$ are a very special case of polynomials in $(\star\star)$. A nice
proof of this criterion may be found in a paper of Tverberg entitled "A remark on Ehrenfeucht's criterion for irreducibility of polynomials". Unfortunately, if you have a polynomial with mixed monomials then this criterion does not apply.  
A: I have a reference for the method mentioned by David Speyer above (sorry couldn't find how to add comment to existing answer):
S. Gao, Absolute irreducibility of polynomials via newton polytopes, link
A: I think there must be a lot of work on irreducibility criteria, although I have unfortunately never seen anything like a unified treatment.  
The first thing that my MathSciNet search turned up was:

Ayad, Mohamed
Sur les polynômes $f(X,Y)$ tels que $K[f]$ est intégralement fermé dans $K[X,Y]$. (French) [Polynomials $f(X,Y)$ such that $K(f)$ is integrally closed in $K[X,Y]$]
Acta Arith. 105 (2002), no. 1, 9--28.
MathSciNet review by Maurice Mignotte:
As indicated in the title, the author studies polynomials $f(X,Y)$ such that $K[f]$ is integrally closed in $K[X,Y]$ (then $f$ is said to be closed), where $K$ is of characteristic zero. His main result is the following theorem. Let $f(X,Y)$ be a nonconstant polynomial in $K[X,Y]$. Then $K[f]$ is integrally closed in $K[X,Y]$ if and only if there exists $a\in K$ such that $f(X,Y)+a$ is irreducible over the algebraic closure of $K$.
Indeed, this article contains many other results and also provides a survey of this question. In particular, several examples of families of closed polynomials are given. The case of positive characteristic is studied briefly at the end of the paper. 

Explanation for how I found this: I recalled that my colleague Dino Lorenzini has a paper "Reducibility of polynomials in two variables" (J. Algebra, 1993).  Upon inspection, this paper didn't seem quite in the spirit of your question -- rather, he gives upper bounds on the number of irreducible components in certain families of polynomials -- but it has several citations on MathSciNet.  Ayad's paper is the first.  
