In 1974 Hopcroft and Tarjan showed that Planarity is in polynomial time. That is an understatement- they actually have an O(V) algorithm which one can actually code up. See their paper here.
It has the curious line:
An Algol implementation of the algorithm successfully tested graphs with as many as 900 vertices in less than 12 seconds.
900 nodes in 12 second was fast then but it slow now.
1) How would their algorithm do on todays machines? How does that compare to what Moore's law (for time) would have predicted? Can this help us determine an x such that Moore's law stopped working at year x. I've heard various candidates for x including the notion that the death of Moore's law has been greatly exaggerated. Moore himself is still alive, at the age of 91.
2) Are there better algorithms now? Nothing can beat O(V); however, is there an algorithm with a better constant?
3) Is there a modern implementation of it (or perhaps even an old implementation run on a modern machine)? If so, how fast does it run on 900 nodes? 9000 nodes? 90,000 nodes? 900,000 nodes? Not sure where to stop.
4) The people in the real world who really need to solve this problem fast: (a) do they exist, and (b) if they do exist then what do they use?