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.
https://www.youtube.com/watch?v=1deOVlruc-o#t=13m15s
> 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.
:-(
https://www.wolframalpha.com/input/?i=graph+ln%28n%29%5E3+vs...
- C1 = C2 = 1 => cross-over is 2x10^7
- C1 = 1, C2 = 10 => cross-over is 2x10^10
- C1 = 10, C2 = 1 => cross-over is 1668.2!