# 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?

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.

• Graphs without intersections are called planar graphs. Searching for this might give you a result. You could start with a planar graph and then move the vertices around for your game.
– w l
Apr 10 '18 at 15:02
• @wl OP does not describe planar graphs though. The requirement that the lines be straight comes in addition. Apr 10 '18 at 16:45
• Any graph that can be drawn in the plane using curves with 0 crossings can also be drawn with 0 crossings using straight lines. The same can be said if you replace '0' with 1,2, or 3. This is no longer true for four or more crossings, and the rectilinear crossing number can be greater than the topological crossing number. For planar graphs, though, the two definitions of the class are equivalent. Apr 10 '18 at 17:01
• chiark.greenend.org.uk/~sgtatham/puzzles/js/untangle.html Apr 10 '18 at 20:56
• @Taemyr, Couldn't we take the top and bottom nodes of the G-H graph, and pull them to the upper and lower right far enough that the curve connecting them can be changed to a straight line? Apr 10 '18 at 21:38

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.

• Note that that's not a sufficient condition, though. Apr 10 '18 at 15:36
• Yeah, I realised that too. But if it doesn't satisfy the inequality, it will never work, right? Apr 10 '18 at 15:40
• Yep, that's right. Apr 10 '18 at 15:40
• The Goldner–Harary_graph is a planar graph that does not satisfy OP's conditions. Apr 10 '18 at 16:49
• @Taemyr yes, it's not regular. Apr 10 '18 at 16:52

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,

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.

• Also note OP required at least two neighbours. Basically, under OP's original conditions, you are stuck with either at most 5 nodes, or exactly 2 neighbours. Your modification is a big improvement, even if it can not create every possible planar graph. Dec 6 '18 at 3:09

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

• I want to find whether there will always be a solution if you connect the nodes randomly but as the same time making sure that each node has at least 2 and at most $m$ connections. See the edit. Apr 10 '18 at 15:12
• Sorry I don't get it. Your title mentions "at most m" but all your drawings use exactly m connections. Apr 10 '18 at 15:20
• My program will randomly construct a graph that has n nodes and each node will have between 2 and m connections. I want to know for what values of n and m, the randomly generated graph is guaranteed to be planar. Using exactly m connections is just an extreme case. Apr 10 '18 at 15:25
• Then what you are looking for are the planarity criteria Apr 10 '18 at 16:00
• @xhienne No. The requirement that the nodes are connected by straight lines is stricter than graphs. Apr 10 '18 at 16:48