10
$\begingroup$

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$

enter image description here

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$:

enter image description here

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:

enter image description here

$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:

enter image description here

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

$\endgroup$
10
  • 5
    $\begingroup$ 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. $\endgroup$
    – w l
    Apr 10, 2018 at 15:02
  • $\begingroup$ @wl OP does not describe planar graphs though. The requirement that the lines be straight comes in addition. $\endgroup$
    – Taemyr
    Apr 10, 2018 at 16:45
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 10, 2018 at 17:01
  • 2
    $\begingroup$ chiark.greenend.org.uk/~sgtatham/puzzles/js/untangle.html $\endgroup$
    – Tin Wizard
    Apr 10, 2018 at 20:56
  • 1
    $\begingroup$ @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? $\endgroup$
    – ilkkachu
    Apr 10, 2018 at 21:38

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ Note that that's not a sufficient condition, though. $\endgroup$
    – Glorfindel
    Apr 10, 2018 at 15:36
  • $\begingroup$ Yeah, I realised that too. But if it doesn't satisfy the inequality, it will never work, right? $\endgroup$
    – Sweeper
    Apr 10, 2018 at 15:40
  • $\begingroup$ Yep, that's right. $\endgroup$
    – Glorfindel
    Apr 10, 2018 at 15:40
  • 1
    $\begingroup$ The Goldner–Harary_graph is a planar graph that does not satisfy OP's conditions. $\endgroup$
    – Taemyr
    Apr 10, 2018 at 16:49
  • 1
    $\begingroup$ Also, it does satisfy the straight line condition. Just take the picture from the Wikipedia page and shift the top and bottom vertex far enough to the right and away from the (vertical) center. $\endgroup$
    – Glorfindel
    Apr 10, 2018 at 16:59
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Dec 6, 2018 at 3:09
5
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Sweeper
    Apr 10, 2018 at 15:12
  • $\begingroup$ Sorry I don't get it. Your title mentions "at most m" but all your drawings use exactly m connections. $\endgroup$
    – xhienne
    Apr 10, 2018 at 15:20
  • $\begingroup$ 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. $\endgroup$
    – Sweeper
    Apr 10, 2018 at 15:25
  • $\begingroup$ Then what you are looking for are the planarity criteria $\endgroup$
    – xhienne
    Apr 10, 2018 at 16:00
  • $\begingroup$ @xhienne No. The requirement that the nodes are connected by straight lines is stricter than graphs. $\endgroup$
    – Taemyr
    Apr 10, 2018 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.