  In this paper we introduce and study discrete analogues of Lebesgue and
Hausdorff dimensions for graphs. It turned out that they are closely related to
well-known graph characteristics such as rank dimension and Prague (or
Ne\v{s}et\v{r}il-R\"odl) dimension. It allows us to formally define fractal
graphs and establish fractality of some graph classes. We show, how Hausdorff
dimension of graphs is related to their Kolmogorov complexity. We also
demonstrate fruitfulness of this interdisciplinary approach by discovering a
novel property of general compact metric spaces using ideas from hypergraphs
theory and by proving an estimation for Prague dimension of almost all graphs
using methods from algorithmic information theory.
