  We introduce a spectral notion of graph complexity derived from the Weyl's
law. We experimentally demonstrate its correlation to how well the graph can be
embedded in a low-dimensional Euclidean space.
