Treksit – Graph theory game | Hacker News Reader

Treksit – Graph theory game

treksit.com

73 pointsthenormal21 comments

Nifty. The arbitrary size of the playfield (and its invisible border) was annoying at times, though.

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)

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.

Fun! This is similar to Simon Tatham's Untangle (http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ and the sgt-puzzles package on Debian systems).

Original version is http://planarity.net/, made by me!

I rewrote it in JavaScript a few years back: https://github.com/tantalor/raphael.planarity

I wanted to say thanks for your game! I loved it when it first came out!

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

Looks like this is just a mashup of Tronix by Danijel Duraković with some other visual effects.

http://pulzed.com/demo/tronix11/

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.

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.

Completely irrelevant and distracting.

loved it. it's interesting how quickly the brain develops a sort of intuition how to solve them after a few levels.

Would be good if there was a leaderboard with times

And here I thought that my years fighting with UML modeling tools would go completely wasted.

I was doing a puzzle and it showed me a button to a "restricted area"- is this normal?

I'm more impressed by the background than the game itself, though both are well done.

what happens after 20? there was nothing?

Easy peasy puzzle

Easy peasy? Isn't graph planarity NP-complete?

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.

Are you thinking graph isomorphism?

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].

[1] http://www.drdobbs.com/planarity-by-edge-addition/184406070

Reply on news.ycombinator.com