Average geodesic distance between two points in the Delaunay graph

As you probably have already reached the correct conclusion, for a Delaunay graph, the magnitude of the average distance between two nodes chosen at random depends on the particular configuration of the points.

Here is an extreme example. Let each of the six sides of the triangular comb have $ n $ edges We will have $ 3n (n + 1) + 1 $ points. The average distance between two nodes is $ Theta (n) $, which $ Theta ( sqrt {3n (n + 1) +1}) $.

We can also consider the row of triangles just above the midline in that honeycomb as a separate graph. Have $ 4n + 1 $ nodes The average distance between two nodes is $ Theta (n) = Theta (4n + 1) $.

It is intuitively clear that for any given Delaunay chart $ N $ points, the average distance between two nodes is between $ Theta ( sqrt {N}) $ Y $ Theta (N) $, which grows much faster than $ O ( log (N)) $, the average distance between two nodes in a small world network. That is evidence of why we call this kind of small world network!