When periodic structures interact with electromagnetic waves amazing features result. In particular, characteristics such as frequency stop-bands, pass-bands and band-gaps could be identified. Surveying the literature, one observes that various terminology have been used depending on the domain of the applications. These applications are seen in filter designs, gratings, frequency selective surfaces (FSS), photonic crystals and band-gaps (PBG), etc. We classify them under the broad terminology of “electromagnetic band-gaps (EBG)”. The focus of this paper is to present a powerful computational engine utilizing finite difference time domain (FDTD) technique integrated with the Prony method to analyze and understand the unique propagation characteristics of different classes of complex EBG structures such as, (a) FSS structures, (b) PBG crystals, (c) smart surfaces for communication antenna applications, (d) surfaces with perfectly magnetic conducting properties (PMC), (e) creation of materials with negative permittivity and negative permeability, (f) surfaces with reduced edge diffraction effects, and (g) the notion of equivalent media. The performance of two types of the EBG structures namely, single and multi-layered tripod FSS, and rectangular, triangular and woodpile PBG crystals is detailed. Some of the potential applications of these structures are highlighted.