Same here. My computer decided to reboot while I was one 12, and lost my progress. I had done the previous three levels in < 15 mins each, though. I think I've got the knack.
I'm intrigued by the graph generation algorithm. Note: Detecting planarity, as well as "planarizing" a planar graph, can be done in polynomial time, though the algorithm is supposed to be quite complicated. See, e.g. this paper.
The simplest way would be to create a known-planar graph, then arrange the vertices in random order in the initial circle, preserving edges. If you assume a simple two-dimensional array, each vertex could have 8 edges, and you're guaranteed not to intersect. Just connect each one together in a chain, then add however many other connections you like at random.
Of course, the cynic in me isn't convinced that anything except the initial placement of the vertices is random - but I'm not curious enough to do the work required to test that theory.
I just meant that the engine only needs to be able to create planar graphs - it doesn't need to be able to create all planar graphs.
Defining points on a two-dimensional grid makes checks for intersections trivial (though you're right - you can't go up to 8 edges/vertex - that was the early hour speaking).
There's your planar graph. Add enough other edges to make the game interesting, shuffle, and display. I played through level 15 today, and while I wasn't specifically looking for it, I don't remember finding any vertices which had more than 4 edges, which implies the grid. (I played through L6 just now to confirm).
I'm not positive that this is what the author's doing - just trying to point out that creating a planar graph is much easier than testing a given graph for planarity. You can make assumptions when building that you can't when analyzing.
Actually, while rearranging, I sorta saw a gridish loking thing.
My strat has been to toss out four vertices to the four corners, and begin rearanging until I form a loop of 4 vertices somewhere in the middle. Toss those 4 to the corners, put everything in one center point, and just start unraveling. It's pretty straight forward from there.
Your idea seems to imply that all I was doing was finding one of the rectangles in the grid, made it the outer rectangle, and unraveling. And, as I look back on the screenshots, your right, it does look like that. There seems to be diagonal "bands" in the final graph that imply the graph started as a grid. I'll have to look at it closer after midterms.
Linear time, to be precise. But, as you say, complicated -- the LEDA folks at least initially decided to write up two planarity tests and if they gave different answers, use a much more expensive but simple algorithm.
Time n^(3/2) is easy using springs (each edge is a spring, then you solve the system using conjugate gradiant). Newer linear solvers run in O(n log n) time """in practice."""
Hmm, I hadn't heard of LEDA before, or these other algorithms (after finding the "most efficient" algorithm fairly quickly, I considered my search complete). Actually, though, after reading your description of their "solution" to the planarity problem, I'm not sure if I can trust them.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
no subject
no subject
no subject
no subject
(past level 4 I gave up)
no subject
no subject
4:34 on lv.6
I don't know if I want to do 8 :/
no subject
no subject
very addictive. I think I need to spread the addiction :)
no subject
I'll be playing it again, I can tell....
no subject
On the plus side, I have absolutely nothing to do on Friday...
no subject
no subject
no subject
I'm intrigued by the graph generation algorithm. Note: Detecting planarity, as well as "planarizing" a planar graph, can be done in polynomial time, though the algorithm is supposed to be quite complicated. See, e.g. this paper.
no subject
Of course, the cynic in me isn't convinced that anything except the initial placement of the vertices is random - but I'm not curious enough to do the work required to test that theory.
(Disclaimer: at a glance)
no subject
I'm not sure what you mean about the vertex-8-edges condition. This isn't a sufficient condition for planarity?
no subject
Defining points on a two-dimensional grid makes checks for intersections trivial (though you're right - you can't go up to 8 edges/vertex - that was the early hour speaking).
There's your planar graph. Add enough other edges to make the game interesting, shuffle, and display. I played through level 15 today, and while I wasn't specifically looking for it, I don't remember finding any vertices which had more than 4 edges, which implies the grid. (I played through L6 just now to confirm).
I'm not positive that this is what the author's doing - just trying to point out that creating a planar graph is much easier than testing a given graph for planarity. You can make assumptions when building that you can't when analyzing.
no subject
My strat has been to toss out four vertices to the four corners, and begin rearanging until I form a loop of 4 vertices somewhere in the middle. Toss those 4 to the corners, put everything in one center point, and just start unraveling. It's pretty straight forward from there.
Your idea seems to imply that all I was doing was finding one of the rectangles in the grid, made it the outer rectangle, and unraveling. And, as I look back on the screenshots, your right, it does look like that. There seems to be diagonal "bands" in the final graph that imply the graph started as a grid. I'll have to look at it closer after midterms.
no subject
Time n^(3/2) is easy using springs (each edge is a spring, then you solve the system using conjugate gradiant). Newer linear solvers run in O(n log n) time """in practice."""
no subject
no subject
no subject