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.