A new millimeter-wave (MMW), electromagnetic band-gap (EBG) structure is presented. The proposed EBG structure without the use of metallic vias or vertical components is formed by etching two slots and adding two connecting bridges to a conventional uniplanar EBG unit-cell. The transmission characteristics of the proposed EBG structure are measured. Results show that the proposed EBG structure has a wide bandgap around the 60 GHz band. The size of the proposed EBG unit-cell is 78% less than a conventional uniplanar EBG, and 72% less than a uniplanar-compact EBG (UC-EBG) operating at the same frequency band. Moreover, and despite the fabrication limitations at the 60 GHz band, the proposed EBG unit-cell provides at least 12% more size reduction than any other planar EBG structures at microwave frequencies. Its enhanced performance and applicability to reduce mutual coupling in antenna arrays are then investigated. Results show a drastic decrease in the mutual coupling level. This EBG structure can find its applications in MMW wireless communication systems.