6 ms·
A new algorithm for graph crossings, hiding in plain sight (2020)
- tromp 5y agoThe 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 agoHow? But, yeah, for large graphs it should be (somewhat) faster.
- deleted 5y ago[deleted]
- goldenkey 5y agoThis 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 agoIn fairness, that's not _that_ huge of a graph.
- zamadatix 5y agoGeneral graph - no. Planar graph you're not sure would remain planar if you added another node - seems pretty large.
- dbaupp 5y agoIt'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 agoUnfortunately, 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. :-(
- monic 5y agoFully dynamic planarity testing in polylogarithmic time https://arxiv.org/abs/1911.03449 https://arxiv.org/abs/1911.03449 https://www.youtube.com/watch?v=1deOVlruc-o https://www.youtube.com/watch?v=1deOVlruc-o
- phaemon 5y agoI like graph theory. You draw some shapes, you draw some lines. It's like the kind of things you can do with your crayons. I reckon kids could be introduced to it earlier in friendlier language.
- xcambar 5y agoWholeheartedly agree. Graph theory is probably one of the most relatable, accessible theories available. It is a fantastic tool to discover algorithmics, as you can visually apply your thinking. FWIW, I personally wrote my master thesis on small world graphs, (_ie_ Kevin Bacon, 6 degrees, that kind of graphs), building structures to add properties to such graphs, and it is, without a doubt, the best memory of my cursus at the university.
- ffhhj 5y agoCan imagine Logo programming lang for graphs.
- js8 5y ago> I reckon kids could be introduced to it earlier in friendlier language. They can be! I remember when I was about 10, I learned about Eulerian paths from a popular math book for kids.
- thomasahle 5y agoI'm pretty sure this is also what draws in a lot of researchers. We're lucky that the theory is also so often useful.
- bmm6o 5y agoSpecifically for planarity, it's pretty easy to convince yourself that K5 and K3,3 are minimally non-planar. You don't come out with a rigorous proof but you do get an intuitive feel. With a decent motivating example it's accessible to kids.
- adrianN 5y agoI also like graph theory. I don't think kids should have to learn it. It's much, much less useful than statistics, linear algebra, and calculus in everyday life or most university courses. Math in schools should, imho, be a mixture of mostly "how to lie with statistics" with a little preparation for engineering and science degrees. People need an intuition for statistical reasoning to understand the news and participate in democracies. It's about as important as being able to read complex texts. You need some calculus and linear algebra to understand basic physics. Most other areas of math are primarily interesting to Mathematicians and Computer Scientists.
- throwaway81523 5y ago(2020). Not saying that to be pedantic but want to distinguish the post from one announcing a new result that hasn't yet sunk into the CS world.
- lostmsu 5y agoWhat are some practical uses for an algorithm like that?
- roachpepe 5y agoWell for one, this discovery could help humanity with Untangle!! https://lagged.com/play/842/ https://lagged.com/play/842/
- asimpletune 5y agoTo find short circuits of a theoretical chip. Basically any time you want to know if wires get crossed.
- _pdp_ 5y agoKnowledge graphs are so under-utilised for practical things despite the fact that there is significant amount of useful research out there. Their problem is that they are expensive. I hope further research in ML would help elevate their relevance significantly. I am particularly fond of using knowledge graphs and graph theory for security related work.
- tomerv 5y agoThis article is about planar graphs, which aren't really related to knowledge graphs.
- not2b 5y agoOf course the constant terms matter, but sqrt(N) < log2(N)^3 up until billions of nodes. For 2*32 nodes sqrt(N) is 2^16 and log2(N)^3 is 2^15. We deal with graphs of that size in electronic design automation, and planar graphs don't need metal crossovers, but we aren't adding one connection at a time. So this result in itself isn't going to be terribly applicable, but may lead to further insights and development of improved graph algorithms.
- thomasahle 5y agoI work with the researchers, and I think they'll be interested in knowing which version of the problem practitioners like yourself are most interested in. Do you ever add/remove edges, perhaps in bulk? Or do are you mostly interested in finding "best possible" layouts for static datasets?
- not2b 5y agoI don't work on placement problems, though part of my work provides input for the placement problem (produce an optimized logic netlist that then has to be placed and routed). But if I can suggest something in the same ballpark: imagine that you have a large graph and you want to partition it into a small number of partitions (say, 4 to 10) of similar size. You want each partition to be a planar graph, and you want the number of interconnects between these graphs to be minimal. The graphs would correspond to metal layers on an ASIC. There's a lot of fuzziness in the way I stated it; to make it more rigorous a suitable cost function would need to be defined.
- thomasahle 5y agoThat sounds like a nice problem: Partition the vertices into planar sub-graphs, minimizing the number of edges between parts. It's not really a dynamic problem anymore. It also becomes very specific to ASIC. Do you know if it has already been studied?
- orange3xchicken 5y ago
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]