A plane-wave-expansion method suited to the analysis of surface-acoustic-wave propagation in two-dimensional piezoelectric phononic crystals is described. The surface modes of a square-lattice Y-cut lithium niobate phononic crystal with circular void inclusions with a filling fraction of 63% are identified. It is found that a large full band gap with a fractional bandwidth of 34% exists for surface acoustic waves of any polarization and incidence, coincidentally with the full band gap for bulk waves propagating in the plane of the surface. The excitation of surface acoustic waves by interdigital transducers is discussed.