[deleted]
A new algorithm for graph crossings, hiding in plain sight (2020)
31–40 of 44 posts
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#32Of 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 i…
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?
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.
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#33I 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 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.
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#34I 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.
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!
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#35I 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 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 particip…
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.
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#36Earlier quoted context omitted.
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 particip…
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.
You are probably referring to
https://en.wikipedia.org/wiki/Dynamic_Bayesian_network
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#37Earlier quoted context omitted.
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.
You are probably referring to https://en.wikipedia.org/wiki/Dynamic_Bayesian_network
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#38The 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.
:-(
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#39Earlier quoted context omitted.
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 particip…
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.
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.
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#40Earlier quoted context omitted.
You are probably referring to https://en.wikipedia.org/wiki/Dynamic_Bayesian_network
Found it: https://mathenchant.wordpress.com/2017/08/16/prof-engels-mar...
Wowzers: https://youtu.be/Ap5NslpYikU
Very interesting stuff..Engel's probability abacus.