My original question is rather vague so I'll start with a precise example and then indicate possible generalisations.

Given a n-tuple $x=(x_1,\dots,x_n)$ in, say, a square with side-length $1$ in the plane, a non-crossing (straight-line) graph on $x$ is a set of segments $[x_i,x_j]$ that pairwise don't intersect except maybe at extremities. What is (an upper bound on) the mean length of such segments, i.e. the average length one gets by measuring the total length of such a graph chosen uniformly at random?

The idea behind this question is that given two points $[x_i,x_j]$, when the length $|x_i-x_j|$ is large, then $[x_i,x_j]$ is not likely to belong to many non-crossing graphs, because the presence of the edge $[x_i,x_j]$ forbids the presence of the many edges that intersects it. In other words, when an edge is large, it is not likey to belong to the graph picked at random, and subsequently this graph will contain mostly small edges, and have a small length. A very adventurous conjecture would be for instance that the mean length is uniformly bounded in $n$, and this conjecture can be milded by assuming additionally that the points are also random, chosen uniformly and independently in $[0,1]^2$.

There are many ways to formulate differently this question, or in different settings, such as

-by replacing "non-crossing graph" by "non-crossing triangulation", "non-crossing pseudo-triangulation", non-crossing pseudo-cycle", or any popular specific subclass of non-crossing graphs.

-by assuming that the points are in some sense nicely distributed (e.g. not too much concentrated in a given region of space)

-by assessing the probability that a specific edge $[x_i,x_j]$ belongs to the uniform graph depending on its length, the number of other segments it intersects, or other geometric-related features of the edge.

Any related reference or idea is welcome.


1 Answer 1


It can be no better that $O(n)$. If you call your pts $(X_i,Y_i)$ and order them by increasing $Y_i$ you get a non-crossing graph by connecting them in that order. As this is no constraint on the $X_i$ the expected distance between one and the next is $O(1)$.

  • $\begingroup$ My question is on the mean length of a graph chosen uniformly at random, not the maximum length by picking a graph by hand. $\endgroup$ Commented May 27, 2014 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.