Re:Treksit – Graph theory game
by thenormal on Tuesday December 06, 2016 @01:12PM
(#13116866)
Easy peasy puzzle
[ Parent
| on HN ]
Easy peasy? Isn't graph planarity NP-complete?
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
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).
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?