A new algorithm for graph crossings, hiding in plain sight (2020)(quantamagazine.org)
quantamagazine.org
A new algorithm for graph crossings, hiding in plain sight (2020)
https://www.quantamagazine.org/a-new-algorithm-for-graph-crossings-hiding-in-plain-sight-20200915/?s=feedly
43 comments
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.
Unfortunately, it looks like there is a large hidden constant in there:
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.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.
:-(
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...
https://www.wolframalpha.com/input/?i=graph+ln%28n%29%5E3+vs...
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!
- 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!
Fully dynamic planarity testing in polylogarithmic time
https://arxiv.org/abs/1911.03449
https://www.youtube.com/watch?v=1deOVlruc-o
https://arxiv.org/abs/1911.03449
https://www.youtube.com/watch?v=1deOVlruc-o
Of 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.
I 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?
I 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.
That 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?
It's not really a dynamic problem anymore. It also becomes very specific to ASIC. Do you know if it has already been studied?
Someone correct me, but I think hMetis is one popular software/algorithm for multi-level graph/hypergraph partitioning. There is also KaHyPar which is a bit more academic.
I'm not current on this stuff at all, but I think planarity mattered more in the Mead-Conway era than today. Modern chips have lots of separate metallization layers so you can avoid crossings. Vias aren't free, but they exist so you can use them.
Practical edge crossing minimization for large graphs (e.g. a billion nodes) is a really hard problem.
An alternative formulations that's seen some use in graph drawing & circuit design software is to describe the embedding problem as an optimization problem: find an assignment of coordinates to nodes such that the edges (line segments) don't cross.
It turns out that estimating a lower-bound on the # of edge crossings of an embedded graph is equivalent to solving an SVM-type problem, and one can characterize the optimal layout as the solution to a nonlinear optimization problem. What's typically done, though, is to alternate between finding the bound for a fixed embedding & optimizing the embedding with something like gradient descent.
It gets a bit more confusing once you realize ic netlists are hypergraphs, and edges correspond to sets of nodes, (e.g. the "embedding" of an edge of a set of nodes is sometimes modeled as a rectilinear steiner tree).
For edge crossing/congestion minimization, the authors are Shabeer "Edge crossing minimization", Spindler "Congestion driven placement/RUDY", RePlace for a sota academic force-directed placement algorithm.
It turns out that estimating a lower-bound on the # of edge crossings of an embedded graph is equivalent to solving an SVM-type problem, and one can characterize the optimal layout as the solution to a nonlinear optimization problem. What's typically done, though, is to alternate between finding the bound for a fixed embedding & optimizing the embedding with something like gradient descent.
It gets a bit more confusing once you realize ic netlists are hypergraphs, and edges correspond to sets of nodes, (e.g. the "embedding" of an edge of a set of nodes is sometimes modeled as a rectilinear steiner tree).
For edge crossing/congestion minimization, the authors are Shabeer "Edge crossing minimization", Spindler "Congestion driven placement/RUDY", RePlace for a sota academic force-directed placement algorithm.
n=nodes>0; n^0.5=(log n)^3, n~24128091.7 , which is millions not billions?
https://www.wolframalpha.com/input/?i=sqrt%28n%29%3D%28log+n...
You're using natural log, for my quick-and-dirty I used log2, which gives a slightly higher crossover point. The exact crossover depends on the size of the constant term, of course.
https://www.wolframalpha.com/input/?i=sqrt%28n%29%3D%28ld+n%... indeed goes to 620 Mio
[deleted]
(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.
I 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.
I reckon kids could be introduced to it earlier in friendlier language.
Wholeheartedly 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.
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.
Can imagine Logo programming lang for graphs.
I 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.
I aggree that statistics is important, but graphs are of some use in statistics:
https://en.m.wikipedia.org/wiki/Graphical_model
Can’t find the link now, but I’ve seen a pedagogical framework for learning basic probability by manipulating dynamic graph-“walking”. Absolutely useable with kids.
https://en.m.wikipedia.org/wiki/Graphical_model
Can’t find the link now, but I’ve seen a pedagogical framework for learning basic probability by manipulating dynamic graph-“walking”. Absolutely useable with kids.
Yeah graphs are often useful for modelling, but typically you need very little basic graph theory to use them for that purpose. Diestel [1] for example spends dozens of extremely dense pages just to introduce the basic terminology. To cover the contents just of the first six chapters (which I consider to be the basics for algorithmic applications of graphs) you'd probably fill most of the highschool math curriculum, even if you skip almost all proofs.
[1] http://diestel-graph-theory.com/basic.html?
[1] http://diestel-graph-theory.com/basic.html?
You are probably referring to
https://en.wikipedia.org/wiki/Dynamic_Bayesian_network
Wowzers: https://youtu.be/Ap5NslpYikU
Very interesting stuff..Engel's probability abacus.
Very interesting stuff..Engel's probability abacus.
Yes, I actually had a graph theory session with 6 year olds ! We talked about graphs, graph coloring, eulerian paths, etc all with pencils and paper. It was a 'talk about your job to schoolchildren' day, and I thought they might relate to graphs.
It was so successful that all kindergarten teachers in the same school started doing it as well.
The unexpected part was the other parents, who looked at the poster the children had made about chromatic numbers complete with examples : quite sadly, they were a lot more scared than their children!
It was so successful that all kindergarten teachers in the same school started doing it as well.
The unexpected part was the other parents, who looked at the poster the children had made about chromatic numbers complete with examples : quite sadly, they were a lot more scared than their children!
> 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.
They can be! I remember when I was about 10, I learned about Eulerian paths from a popular math book for kids.
As someone who hated math and was really bad at it since calculus (mostly due to lack of rigor), yes. Once I got to algorithms class, I struggled at first but after a session with my (really excellent) professor, something “clicked”.
I really think graph theory and discrete math in general should be taught much earlier. Maybe even before (or alongside) calculus in high school. Calculus isn’t really a legitimate prerequisite in this case.
I really think graph theory and discrete math in general should be taught much earlier. Maybe even before (or alongside) calculus in high school. Calculus isn’t really a legitimate prerequisite in this case.
Specifically 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.
I'm pretty sure this is also what draws in a lot of researchers. We're lucky that the theory is also so often useful.
[deleted]
What are some practical uses for an algorithm like that?
To find short circuits of a theoretical chip. Basically any time you want to know if wires get crossed.
Well for one, this discovery could help humanity with Untangle!!
https://lagged.com/play/842/
https://lagged.com/play/842/
[deleted]
[deleted]
Knowledge 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.
This article is about planar graphs, which aren't really related to knowledge graphs.