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?
The boost library implements planarity testing (and much more btw) in linear time if memory serves me right. None of the linear time planarity testing algorithms are simple.
ReplyDeleteI asked about poly time algorithms for planarity here; seems like there's a trade-off between the simplicity of the algorithm and the depth of the theorems it uses: https://cstheory.stackexchange.com/questions/24962/what-is-simplest-polynomial-algorithm-for-planarity
ReplyDeleteChip designers on Flatland!
ReplyDeleteMore seriously, this seems a bit like "laying out" a circuit on a VLSI chip. But actual chips have multiple layers, and no doubt lots of other constraints (such as lengths of wires), so I'd say this is only vaguely related.