Cellular structures like honeycombs or reticulated micro-frames are widely used in sandwich construction because of their superior structural static and dynamic properties. The aim of this study is to evaluate the dynamic behavior of two-dimensional cellular structures, with the focus on the effect of the geometry of unit cells on the dynamics of the propagation of elastic waves within the structure. The characteristics of wave propagation for the considered class of cellular solids are analyzed through the finite element model of the unit cell and the application of the theory of periodic structures. This combined analysis yields the phase constant surfaces, which define the directions of waves propagating in the plane of the structure for the assigned frequency values. The analysis of iso-frequency contour lines in the phase constant surfaces allows the prediction of the location and extension of angular ranges, and therefore regions within the structures where waves do not propagate. The performance of honeycomb grids of regular hexagonal topology is compared with that of grids of various geometries, with the emphasis on configurations featuring a negative Poisson's ratio behavior. The harmonic response of the considered structures at specified frequencies confirms the predictions from the analysis of the phase constant surfaces and demonstrates the strongly spatially-dependent characteristics of periodic cellular structures. The numerical results presented indicate the potentials of the phase constant surfaces as tools for the evaluation of the wave propagation characteristics of this class of two-dimensional periodic structures. Optimal design configurations can be identified in order to achieve the desired transmissibility levels in specified directions and to obtain efficient vibration isolation capabilities. The findings from the presented investigations and the described analysis methodology will provide invaluable guidelines for the prototyping of future concepts of honeycombs or cellular structures with enhanced vibro-acoustics performance.