We recently reported on the realization of ultraviolet photonic crystal laser based on zinc oxide [Appl. Phys. Lett. 85, 3657 (2004)]. Here we present the details of structural design and its optimization. We develop a computational supercell technique that allows a straightforward calculation of the photonic band structure of ZnO photonic crystal slab on sapphire substrate. We find that despite the small index contrast between the substrate and the photonic layer, the low-order eigenmodes have predominantly transverse-electric (TE) or transverse-magnetic polarization. Because emission from ZnO thin film shows a strong TE preference, we are able to limit our consideration to TE bands, spectrum of which can possess a complete photonic band gap with an appropriate choice of structure parameters. We demonstrate that the geometry of the system may be optimized so that a sizable band gap is achieved. ©2005 American Institute of Physics