Creating Planar Graphs on Roblox

Hi there! So I have created this puzzle thingy that is a replica of the puzzle game Untangled, where there are a bunch of randomly generated points and lines, which you have to move so that each line is no longer touching another. Here is a video of what I have made so far:

Sorry, the file is pretty big so I uploaded it on twitter. let me know if you can’t see it.

Here is a quick gyazo gif if you can’t see the above:

So my current system is capable of generating random lines, but it is not capable of calculating whether it is solveable, and how to solve it. It also can’t detect when a puzzle has been solved. So this question should be split into 3 smaller parts:

  1. How to calculate whether a puzzle is solvable.

  2. How can a script solve it. (Would be nice to have, but not neccesary)

  3. How can it check for a completed puzzle

So while doing some research, I found out that the untangle puzzle uses something called planar graphs in plotting each point and caluclating how many lines to come off it. I still don’t exactly understand how it works however, and I am not sure whether something like this could be accomplished on roblox. (Hopefully it can, I’ve already spend a good chunk of time working on what I have so far lol)

Here is my script so far that generates the lines:

local MaxConnections = 4
local function LoadLines()
	for i,v in pairs(script.Parent:GetChildren()) do
		if v:IsA("Frame") then
			if v.Name ~= "Ignore" then
				local connections = v.Folder
				local Possible = true
				local tries = 0
				local Maxtries = (#script.Parent:GetChildren()) - 1
					if #(v.Folder:GetChildren()) < MaxConnections then
						for o,p in pairs(script.Parent:GetChildren()) do
							if p.Name ~= "Ignore" then
								if p:IsA("Frame") and p ~= v then
									local canconnect = true
									for q,w in pairs(connections:GetChildren()) do
										if w.Value == p then
											canconnect = false
									if #(p.Folder:GetChildren()) >= MaxConnections then
										canconnect = false
									if canconnect == true then
										local NewObject ="ObjectValue")
										NewObject.Parent = connections
										NewObject.Value = p
										local NewObject2 ="ObjectValue")
										NewObject2.Parent = p.Folder
										NewObject2.Value = v
										local Frame ="Frame")
										Frame.Name = "Ignore"
										Frame.Parent = Parent
										Frame.AnchorPoint =, 0.5)
										local F1 = v
										local F2 = p
										Moveconnections[#Moveconnections+ 1] = RS.RenderStepped:Connect(function()
											local XLength = F1.AbsolutePosition.X - F2.AbsolutePosition.X
											local YLength = F1.AbsolutePosition.Y - F2.AbsolutePosition.Y
											local Mag = (
		, F1.AbsolutePosition.Y) 
												-, F2.AbsolutePosition.Y)
											local CenterPosition = (F2.AbsolutePosition + F1.AbsolutePosition) / 2
											Frame.Rotation = DivideSmaller(XLength, YLength)
											Frame.Position = UDim2.fromOffset(CenterPosition.X + 15, CenterPosition.Y +15)
											Frame.Size = UDim2.fromOffset(Mag.Magnitude, 1)



						Possible = false
					tries  = tries + 1
					if tries == Maxtries then
						Possible = false
				until #connections:GetChildren() == MaxConnections or Possible == false


Sorry if it is a bit messy

But as you can see, it currently uses folders to see how many connections it currently has. So I want to know if there is a way to calculate everything all at once.

I appreciate any answers :slight_smile:

They actually published a journal article on it.

In 2014, mathematician David Eppstein published a paper[15] providing an effective algorithm for solving planar graphs generated by the original Planarity game, based on the specifics of the puzzle generation algorithm.

Here is the article, seems complicated

I believe you can get away doing something simpler by detecting lines crossing if you think of each line as a piecewise cartesian line.


1 Like

I think the article states how to solve a puzzle once it has been create, while it is helpful, I think instead of doing that I should be following whatever algorithm the puzzle uses to generate the puzzle.

As for the detecting lines, do you have any examples of how I might achieve this? I’m not to create with this stuff XD