# Mean geodesic distance between two points in Delaunay Graph

If I have a Delaunay Graph, what is the mean geodesic distance between two randomly chosen nodes. I know that in a small world network, it is in O(log(N)), with N being the number of nodes.

Thank you!

• The Small World network is just an example, it doesn't have anything to do with the Delaunay graph. I know the result for a Small World, but I do not knowthe answer for a Delaunay Graph – Adrien Nivaggioli Dec 10 '18 at 17:02
• Do you mean the least number of edges in a path or the (planar) Euclidean distance by "geodesic distance between two nodes"? – John L. Dec 10 '18 at 17:17
• Yes, I understood that the geodesic distance in a graph is the number of nodes (or edges) traversed in the shortest path between two nodes! Sorry that is not true ! – Adrien Nivaggioli Dec 10 '18 at 17:18

Here is one extreme example. Let each one of the six sided of the triangulated honeycomb have $$n$$ edges. We will have $$3n(n+1)+1$$ points. The average distance between two nodes is $$\Theta(n)$$, which is $$\Theta(\sqrt {3n(n+1)+1})$$. We can also consider the row of triangles just above the middle line in that honeycomb as a separate graph. It has $$4n+1$$ nodes. The average distance between two nodes is $$\Theta(n)=\Theta(4n+1)$$.
It is intuitive clear that for any given Delaunay graph of $$N$$ points, the mean distance between two nodes is between $$\Theta(\sqrt{N})$$ and $$\Theta(N)$$, which grows much faster than $$O(\log(N))$$, the mean distance between two nodes in a small-world network. That is one evidence why we call that kind of network small world!