The previously best known algorithm for deciding if a given edge could be added to a planar n-node graph, while keeping it planar, took time O(sqrt(n)).
The new algorithm needs time only O((log n)^3), an exponential speedup.
> By considering a lot of cases, find O(1) candidates to the flip nearest u that improves the embedding.
Also a comment underneath by one of the authors:
> We have not tested it (yet), but I suspect the current version will be too slow in practice due to the ~400 cases it has to check for each flip. Also, some of the core data structures we use do not yet have a good practical implementation. I do plan on making an implementation at some point, but that could be months or years away.
It's somewhat meaningless to compute exact cross-overs for big-O complexities without the constant factors. That is, the actual times for the algorithms are C1 * sqrt(n) + ... and C2 * log(n)^3 + ..., where the ... are lower-order terms. The exact ratio of C1 and C2 (and even the lower-order terms) can have a large impact on the crossover:
