Maximum number of non crossing line segments endpoints chosen in a random set of points in the plane

Question

Given a set of n randomly scattered points for even n = 2,4,6,...,50 . Find the maximum number of line segments between the pairs of nodes in such a way these line segments do not cross each other.

Answer 1

As stated in my comment, if you use every vertex exactly once, then you obtain $\frac n2$ edges, which is boring.

Otherwise you might want to look at Euler's formula which tells you that in order to maximize the number of edges, you also want to maximize the number of faces. So how many faces can there be? Looking at OEIS, and using the right search terms, you may find A008486

Expansion of $\displaystyle\frac{1+x+x^2}{(1-x)^2}$:
1, 3, 6, 9, 12, 15, 18, 21, …

with the following comment:

Conjecture from Dmitry Kamenetsky, Jun 29 2008: This is also the maximum number of edges possible in a planar simple graph with $n+2$ vertices.

The conjecture is correct. Proof: For $n=0$ the theorem holds, the maximum planar graph has $n+2=2$ vertices and $1$ edge. Now suppose that we have a connected planar graph with at least $3$ vertices. If it contains a face that is not a triangle, we can add an edge that divides this face into two without breaking its planarity. Hence all maximum planar graphs are triangulations. Euler's formula for planar graphs states that in any planar simple graph with $V$ vertices, $E$ edges and $F$ faces we have $V+F-E=2$. If all faces are triangles, then $F=\frac{2E}3$, which gives us $E=3V-6$. Hence for $n>0$ each maximum planar simple graph with $n+2$ vertices has $3n$ edges. – Michal Forisek, Apr 23 2009

One problem here is the fact that your graph has to be not only planar, but straight-edged. The above argument is still easy to see for all faces except the exterior one. So in order to use this result, you'll still have to show that you can always make the outer face a triangle as well. The easiest approach to this effect is probably starting out with an outer triangle, and then successively subdividing it, each additional vertex adding three edges and dividing an existing triangle into three new triangles.

But taking a closer look at your problem, there is this statement about points being “randomly scattered”. Which means you are not free to choose the locations of the outer points. In which case the number of vertices of the outer face is predetermined: it is the number of points in the convex hull of your input. The interior you could always triangulate, so you can give the resulting number of edges as a function of both the total number of points and the number of points in the convex hull. I don't see how the number of points being even might be relevant to all of this.