We indeed don't need to embed the vertices in anything, however, computing dimensionality is slightly more complicated than you described. You need to consider balls (graph neighborhoods) of different radii starting from the same vertex, and see how quickly their volumes (vertex counts) grow. If they grow as a third power of the radius, for example, we have a 3-dimensional space.
