News for hackers. Stuff that matters.
Re:Treksit – Graph theory game by thenormal on Tuesday December 06, 2016 @01:12PM (#13116866)
Easy peasy puzzle
Re:Treksit – Graph theory game by tptacek on Tuesday December 06, 2016 @02:33PM (#13117564)
Easy peasy? Isn't graph planarity NP-complete?
Re:Treksit – Graph theory game by karlding on Tuesday December 06, 2016 @07:06PM (#13119401)
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

Re:Treksit – Graph theory game by Someone on Tuesday December 06, 2016 @02:51PM (#13117703)
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 by quantumtremor on Tuesday December 06, 2016 @02:44PM (#13117653)
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 by gravypod on Tuesday December 06, 2016 @02:42PM (#13117637)
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.
Re:Treksit – Graph theory game by GFK_of_xmaspast on Tuesday December 06, 2016 @03:19PM (#13117924)
Are you thinking graph isomorphism?