Treksit – Graph theory game
treksit.com
Treksit – Graph theory game
1–10 of 24 posts
Re: Treksit – Graph theory game
#2Easy peasy puzzle
Re: Treksit – Graph theory game
#3Easy peasy puzzle
Easy peasy? Isn't graph planarity NP-complete?
Re: Treksit – Graph theory game
#4Re: Treksit – Graph theory game
#5Fun! This is similar to Simon Tatham's Untangle (http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ and the sgt-puzzles package on Debian systems).
Re: Treksit – Graph theory game
#6Easy peasy puzzle
Easy peasy? Isn't graph planarity NP-complete?
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).
Re: Treksit – Graph theory game
#7Fun! 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
Re: Treksit – Graph theory game
#8Re: Treksit – Graph theory game
#9Easy peasy puzzle
Easy peasy? Isn't graph planarity NP-complete?
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.
Re: Treksit – Graph theory game
#10Nice. 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 :)