Yea the problems were completely no problem! Jokes asside there is a large difference between spacial thinking in the human brain and computationally intense tasks.
Definitely not. Here's a nice algorithm that will actually compute the embedding as well: https://en.wikipedia.org/wiki/Fáry's_theorem. However straight line embeddings by Fary's theorem can sometimes be much larger than necessary, more recent advancements in computational geometry can compute embeddings with guarantees of much smaller drawings (small wrt the area of the bounding box of the drawn graph).
The player doesn't have to decide whether the graph is planar, but has to find a planar embedding of a planar graph. That's fairly easy; a greedy algorithm that removes crossings at every move mostly seems to do the trick.
I think a more interesting game would be to have the player decide whether a graph is planar, with more points scored (or lost, if he answers incorrectly) the fewer moves he makes.
No, graph planarity can be determined using Kuratowski's theorem, which essentially states that a graph is planar if and only if it doesn't contain K_{5} or K_{3, 3}.
I believe the planarity test algorithm has been improved, such that it can be done in O(n) using the edge addition method [1].
Nice. Went through maybe first 8-10, but it becomes boring without some kind of 'progress bar'. How long before something happens? Will it become harder with time, or what? A commentary or some hint at what's next would be interesting :)
J age 11yo says it's "cool-a-rooney". Personally I liked it, but the instructions were too terse to get us started properly and the hyperspeed thing is a little strange, I assume it's just a distraction?
One problem we had was that J opened the menu at the bottom of the [small] playing area, that covered the "right arrow" that moves on to the next map. It wasn't obvious how to get back to playing, the "play" button didn't close the menu and the collapse arrow wasn't visually apparent.
There is a reset button if you click the upward-pointing arrow at the bottom of the playfield then the "play" icon.
Also loved this game. Found it challenging - seems like a good starting point is to find the nodes with the least links and put them around the edge, maintaining all the symmetries you can. Love the feeling of inversion that you get when you eliminate a load of crosses in one move.
Nice game, but as others have mentioned, the game area is way too small, and you need to able to move the entire graph as one, as you often get points placed towards a corner when you are trying out different positions of points.
Also the "restricted area" link with the "Bonus" alt-text feels like it takes you on a bit of a spammy ride. I tried it, and it took me to a site that said something about randomly generated music and a link with the text "show me something cool", which took me to yet another page, in yet another window with a bunch of animated dots.
23 comments
[ 3.2 ms ] story [ 70.6 ms ] threadI think a more interesting game would be to have the player decide whether a graph is planar, with more points scored (or lost, if he answers incorrectly) the fewer moves he makes.
I believe the planarity test algorithm has been improved, such that it can be done in O(n) using the edge addition method [1].
[1] http://www.drdobbs.com/planarity-by-edge-addition/184406070
I rewrote it in JavaScript a few years back: https://github.com/tantalor/raphael.planarity
http://pulzed.com/demo/tronix11/
One problem we had was that J opened the menu at the bottom of the [small] playing area, that covered the "right arrow" that moves on to the next map. It wasn't obvious how to get back to playing, the "play" button didn't close the menu and the collapse arrow wasn't visually apparent.
More suggestions:
* A reset button when things get too messed up
* A "check my work" button that highlights errors, which can be hard to see when there get to be a lot of points and edges
* Ability to select and drag multiple points (particularly useful when you need to shift an entire section over to have more room to work
* A clearer explanation of the UI (I was reluctant to click on the diamond icons for fear of losing my progress)
* Some sort of ending (even just a "Congratulations" message)
Also loved this game. Found it challenging - seems like a good starting point is to find the nodes with the least links and put them around the edge, maintaining all the symmetries you can. Love the feeling of inversion that you get when you eliminate a load of crosses in one move.
Would be good if there was a leaderboard with times
Also the "restricted area" link with the "Bonus" alt-text feels like it takes you on a bit of a spammy ride. I tried it, and it took me to a site that said something about randomly generated music and a link with the text "show me something cool", which took me to yet another page, in yet another window with a bunch of animated dots.
Completely irrelevant and distracting.