4 ms·

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

by tromp 5y ago

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.

fuzzybear3965 5y ago
How? But, yeah, for large graphs it should be (somewhat) faster.
- deleted 5y ago
  [deleted]
goldenkey 5y ago
This really only takes effect for very large values of n. The crossover is around 3x10^7 https://www.wolframalpha.com/input/?i=graph+ln%28n%29%5E3+vs+sqrt%28n%29+from+0+to+100000000 https://www.wolframalpha.com/input/?i=graph+ln%28n%29%5E3+vs...
- foota 5y ago
  In fairness, that's not _that_ huge of a graph.
  - zamadatix 5y ago
    General graph - no. Planar graph you're not sure would remain planar if you added another node - seems pretty large.
- dbaupp 5y ago
  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: - 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!
EdSchouten 5y ago
Unfortunately, it looks like there is a large hidden constant in there: https://www.youtube.com/watch?v=1deOVlruc-o#t=13m15s 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. :-(

by tromp 5y ago

fuzzybear3965 5y ago

How? But, yeah, for large graphs it should be (somewhat) faster.

deleted 5y ago
[deleted]

goldenkey 5y ago

This really only takes effect for very large values of n. The crossover is around 3x10^7 https://www.wolframalpha.com/input/?i=graph+ln%28n%29%5E3+vs+sqrt%28n%29+from+0+to+100000000 https://www.wolframalpha.com/input/?i=graph+ln%28n%29%5E3+vs...

foota 5y ago
In fairness, that's not _that_ huge of a graph.
- zamadatix 5y ago
  General graph - no. Planar graph you're not sure would remain planar if you added another node - seems pretty large.
dbaupp 5y ago
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: - 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!

EdSchouten 5y ago

Unfortunately, it looks like there is a large hidden constant in there: https://www.youtube.com/watch?v=1deOVlruc-o#t=13m15s 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. :-(