3 ms·
Easy peasy puzzle
by thenormal 10y ago
Easy peasy puzzle
- tptacek 10y agoEasy peasy? Isn't graph planarity NP-complete?
- gravypod 10y agoYea the problems were completely no problem! Jokes asside there is a large difference between spacial thinking in the human brain and computationally intense tasks.
- quantumtremor 10y agoDefinitely not. Here's a nice algorithm that will actually compute the embedding as well: https://en.wikipedia.org/wiki/Fáry's_theorem 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).
- deleted 10y ago[deleted]
- Someone 10y agoThe 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.
- GFK_of_xmaspast 10y agoAre you thinking graph isomorphism?
- karlding 10y agoNo, 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 http://www.drdobbs.com/planarity-by-edge-addition/184406070