A maximally planar graph (triangulation) with $n$ vertices has 3$n$-6 edges and hence the average degree of the vertices is 6-$\frac{12}{n}$.

Consider the Delaunay triangulation of $n$ vertices that are randomly distributed uniformly in 2D space.

Now the Delaunay triangulation can't be considered as maximally planar since the vertices are fixed in space but it is still planar so we still have the same bound: the average degree is strictly less than 6.

Is there a comparably simple result in terms of the variance of the degree of the vertices?


How can I analytically approach the question, given a Delaunay triangulation of randomly distributed points, what is the probability that a vertex has degree greater or equal to some $k$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.