First, a note on the Bell-Evans-Polanyi (BEP) equation:
The form you've written it in disguises what the constant $\alpha$ tells you. From the wikipedia article, it's said that $\alpha$ is a number between 0 and 1 which tells you how close the transition state is to the reactant state. Thus, this constant actually tells you quite a lot about the shape of potential energy plotted versus the bond coordinate.
To see why this is true, we should look at the derivation given in the article you linked. The BEP equation assumes that the energy of both the reactant and product vary linearly with the bond length of the atom being transferred. This is probably a very bad assumption for finding the actual shape of the well, but the intersection of these two lines seems to give a good approximation for the location of the transition state. Specifically, if one knew the slopes of these lines $m_1$ and $m_2$, we could find $\alpha$ according to $$\alpha=\frac{m_1}{m_1-m_2}.$$
See the wikipedia article you linked for the details on this, but hopefully this motivates the meaning of the constant $\alpha$.
So, what does this have to do with the article you're asking about?
Well, the reaction that is being catalyzed in the figure you have copied is,$$\ce{CO +3H2->CH4 +H2O}$$This seems very unlikely to happen in the gas-phase because the $\ce{CO}$ bond is very strong and we would have to have four molecules collide all at once and magically rearrange their atoms.
Thus, a transition metal surface is used as an adsorption site to get all these atoms close together.
What exactly is on the axes?
Well, now we can see that by the "CO Dissociation Energy" they mean the energy it takes to dissociate the carbon and oxygen atoms once they have been adsorbed onto the metal surface. So, a negative dissociation energy indicates that when $\ce{CO}$ adsorbs, it exists as two separated carbon and oxygen atoms.
Additionally, because they have shown the BEP linear relationship, the slope of that line is $\ce{\alpha}$ and the y-axis is the classical Arrhenius activation energy.
At first, it seems like the best catalyst should be the one which has the smallest CO dissociation energy, but as the article points out,
The reason is that in the limit of weak coupling (Ediss is only a little negative), the BEP relation gives that the barrier for dissociation of the reactants will be high and the rate low. For strong coupling (Ediss very negative) the activation energy of adsorption is small but now the barrier for forming the products will be large.
That is to say, if the reactants adsorb quite strongly to the surface (i.e. Rhenium in the plot) then reaction wil go really slowly because the activation energy (not the on you're seeing on the y-axis here) for forming the intermediates leading to methane will be very high.
On the other hand, if $\ce{CO}$ doesn't adsorb very favorably, the reaction will be slowed down because both $\ce{CO}$ and $\ce{H2}$ need to be adsorbed to react. When they do meet though, because they adsorb weakly, the activation energy to forming the products will be small.
This is why they say,
An optimal interaction strength must exist between these two limits.
The figure below on the right shows this intersection for pure metal surfaces. The closer you are to the peak, the better.
(source: nature.com)
Thus, either Cobalt or Ruthenium would be optimal for his reaction, but as the authors note, these are expensive, so nickel is used in the industrial process. Thus, some kind of alloy which behaves similarly to Ruthenium or Cobalt would be great if it could be found.
Finally, it should be noted that the BEP equation will only work in very specific circumstances where bond stretching is the dominant feature which determines if two things react. Thus, when reactants are adsorbed and thus all they can really do is vibrate, I would expect the BEP equation will do a pretty decent job.
I hope that clarified your questions. Let me know if I missed anything.
