For n nodes that are connected to at most m and at least 2 other nodes, what values of n and m always allow the connections to not intersect?

Question

I am trying to develop a puzzle game where $n$ nodes are generated and placed randomly on the screen. Each node is connected to at most $m$ and at least 2 other nodes by straight lines.

This is an example of $n = 4, m = 3$

The player has to move the nodes so that no straight lines intersect each other. Overlapping lines are counted as intersecting. A solution to the above problem is to move node D into $\Delta ABC$:

I need to know what values of $n$ and $m$ will definitely have a solution.

I tried doing this by drawing $n$ nodes with exactly $m$ connected nodes. I think that if I can find a solution for this, there will also be a solution for the case of "nodes can have at most $m$ connections".

I first tried $n = 5, m = 4$, and could not find a solution.

Then I tried $n = 6, m = 4$, and found this solution:

$n = 7, m = 4$ doesn't seem to have a solution, and neither does $n = 7, m = 5$ and $n = 8, m = 5$. I became quite confused as to what $n$ and $m$ has to be, to always have a solution.

I thought this is related to graph theory, but it seems like graph theory doesn't care about the positions of nodes and whether edges intersect. So I don't even know where to research this kind of problem.

Clarification:

I tried to move the nodes of this graph and can't move them without intersecting lines:

This graph has 5 nodes and each node has 4 connections, so $n = 5, m = 4$ does not always have a solution.

Answer 1

As @wl mentions, the graphs for which this is possible are called Planar graphs. According to Kuratowski's theorem, a graph is planar if and only if it does not 'contain' the complete graph on 5 nodes (your last picture) or the so-called utility graph.

The 'complete' $m, n$ graphs you are making are called $m$-regular graphs. These have $n$ vertices and $\frac{mn}{2}$ edges. One of the theorems on planar graphs state that they have $e \le 3v-6$, where $e$ is the number of edges and $v$ the number of vertices. This implies that $\frac{mn}{2} \le 3n-6$, so $m \le 6 - \frac{12}{n}$. This proves $m = 4, n = 5$ won't work, for $m = 5$ you need to have $n\ge 12$ and the higher $n$ is, the further away you are from equality, so the easier it should be to construct a planar regular graph.

Note that the $m \le 6 - \frac{12}{n}$ condition is not sufficient; this question on our sister site Mathematics shows that the $m = 4, n = 7$ case is impossible.

Also, note that the restriction to straight lines (as opposed to curved lines) has no influence; this is known as Fáry's theorem.

Answer 2

I agree with 'w l' that what you really want to be doing is researching 'planar graphs', but the literal answer to the question you asked is:

for n=5, m must be <4 to guarantee a non-crossing configuration. For n>5, m must be <3. If you divide 6 vertices into two groups of 3, (ABC,DEF) and then connect every pair of vertices that are in different groups,

AD,AE,AF BD,BE,BF CD,CE,CF

every possible arrangement of points will have crossing edges, even if the connections are allowed to be arbitrary curves rather than straight lines.

I was about to elaborate on Kuratowski's Theorem, but that might be redundant, looking above. For an actual proof that a crossing-free drawing in the plane is impossible, rather than just too difficult to find working on only one cup of coffee, see https://www.youtube.com/watch?v=VvCytJvd4H0

However, if you'd like to randomly generate a maximal planar graph (to which no additional edges may be added without forcing a crossing) in a way that could feasibly make every possibility, here's an algorithm that will accomplish that.

First, drop three points on the plane, and connect them with edges. Then, 
randomly generate n-3 points inside this reference triangle, and note the 
order in which they are generated.  In order, connect each point to the 
three vertices of the smallest triangle already drawn that contains it.
(Or equivalently, add every possible edge that doesn't create a crossing.) 

Scramble the locations of the vertices, and there you are! I'm not sure if that's how the original 'Planarity' game did it, but it should get the job done...note that the original n=3 points make 3n-6=3 edges, and every additional point after that creates 3 more edges, so this keeps you exactly at the 3n-6 limit. Demonstrating that every such graph can be made this way is a bit trickier, but I'll dig up a reference if you're interested (I think Steinitz published his proof in 1934, but that's in German...)

EDIT: I actually brain-burped back when I wrote this answer...there are maximal planar graphs which are skipped by this method of construction. Rather, it creates all those whose vertices can be uniquely 4-colored.

Answer 3

Not sure that is the answer you expect but with at least 2 and at most m other nodes there is always a solution with...

m = n - 1

Just place your n nodes in a polygonal fashion and link each node to its two neighbours, you have your "at least 2".
Now choose a node and link it to the n-1 other nodes, and you have your "at most m" with m = n-1