The propagation of photons, electrons and positrons at ultra-high energies above 10^{19} eV can be changed considerably if the dispersion relations of these particles are modified by terms suppressed by powers of the Planck scale. We recently pointed out that the current non-observation of photons in the ultra-high energy cosmic ray flux at such energies can put strong constraints on such modified dispersion relations. In the present work we generalize these constraints to all three Lorentz invariance breaking parameters that can occur in the dispersion relations for photons, electrons and positrons at first and second order suppression with the Planck scale. We also show how the excluded regions in these three-dimensional parameter ranges would be extended if ultra-high energy photons were detected in the future.