In the present paper, generalized Paris and Wöhler equations are derived according to dimensional analysis and incomplete similarity concepts. They provide a rational interpretation to a majority of empirical power-law criteria used in fatigue. In particular, they are able to model the effects of the grain size, of the initial crack length, as well as of the size-scale of the tested specimen on the crack growth rate and on the fatigue life. Regarding the important issue of crack-size dependencies of the Paris' coefficient C and of the fatigue threshold, an independent approach, based on the application of fractal geometry concepts, is proposed to model such an anomalous behavior. As a straightforward consequence of the fractality of the crack surfaces, the fractal approach provides scaling laws fully consistent with those determined from dimensional analysis arguments. The proposed scaling laws are applied to relevant experimental data related to the crack-size and to the structural-size dependencies of the fatigue parameters in metals and in quasi-brittle materials. Finally, paying attention to the limit points defining the range of validity of the classical Wöhler and Paris power-law relationships, correlations between the so-called cyclic or fatigue properties are proposed, giving a rational explanation to the experimental trends observed in the material property charts.