# Maximizing the number of non-crossing lines between a number of points

Suppose I have a number of points in 2-dimensional space. I want to draw as many lines between the points as possible such that no two lines cross.

Hoping for a polynomial time algorithm, I constructed a maximum flow network. Each line between the points in my problem become a node in my maximum flow network. Arcs connect the source to each of the nodes in my flow network. Nodes representing links that do not cross with any other link gets connected straight to the sink with bounds [0,1]. Pairs of nodes representing pairs of lines that are mutually exclusive (crossing lines) are first connected to a dummy node, and then and arc to the sink with bounds [0,1].

At first glance, this seems like a brilliant polynomial-time solution. Unfortunately the maximum flow network doesn't work. Let me illustrate:

Node 1 is incompatible with node 2. Node 2 is incompatible with node 3:

   1 ---O
/      \____ [0,1]
/       /          \____T
S--2 ---O           /
\       \____ [0,1]
\      /
3 ---O


Now, there's nothing stopping flow through node 2 to the sink via the upper dummy node, and flow through node 3 to the sink via the lower dummy node. This means the crossing links constraint is violated and solution is infeasible.

I can construct a very simple integer program:

$$\text{max:} \sum_{i = 1}^{n}X_i\\ \\ X_1 + X_2 <= 1\\ X_2 + X_3 <= 1\\ \text{(etc...)}\\ \\ X_i \in {0,1} \quad i = 1,2,\ldots,n$$

This works exactly as expected, and obviously give the optimal solution. It is very simple to construct this IP, but for very large number of points in the original problem, there is a huge number of potential lines and an enormous number of crossing lines. In short, I can only solve up to about 15 points in any reasonable time.

Can anyone see any obvious reduction that shows that this problem is inherently difficult (i.e. NP-Hard)? Or does there exist a P-Time algorithm that solves this optimally?

-
Straight lines? –  fedja Feb 25 '13 at 4:27
Yes, straight lines. –  AKrip Feb 25 '13 at 4:52

If you have $n$ points, first draw the convex hull. Let's say this has $c$ points. The triangulation will have $e$ edges (these are your lines), with $2e=3f+c$, and $f-e+n=1$, where $f$ is the number of triangles. Eliminating $f$, we get $2e=3e-3n+3+c$, or $e=3n-3-c$.