We consider the two-component dielectric medium consisting of a periodic array of parallel air columns of square cross section embedded into a lossless optically dense host material with the dielectric constant ζ > 1. We show that if ζ is large enough and the relative distance δ between the air columns is such that ζδ ≫ 1 and ζδ2 ≪ 1, then the corresponding Maxwell operator has a series of gaps in the spectrum. We also provide some analytic formulas that enable one to detect location of bands and gaps in the spectrum. In particular, the typical wavelength exhibiting a photonic band gap is 2πL√ζδ, where L is the distance between the axes of adjacent air columns. We also give some estimates on the space distribution of electric field energy for different eigenmodes.