4 ms·
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
by Someone 10y ago
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.