[HN Gopher] A New Algorithm for Graph Crossings, Hiding in Plain...
___________________________________________________________________
A New Algorithm for Graph Crossings, Hiding in Plain Sight
Author : panabee
Score : 96 points
Date : 2021-05-26 18:39 UTC (4 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| not2b wrote:
| 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.
| thomasahle wrote:
| 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?
| not2b wrote:
| 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.
| potiuper wrote:
| 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...
| not2b wrote:
| 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.
| senkora wrote:
| OP specified log2 instead of the natural log, which gives us
| ~621,201,921.4
|
| Still not billions but much closer. Of course, choice of base
| is a constant factor. But the conversion factor is raised to
| the ninth power because we have sqrt(n) on the LHS and the
| log term raised to the third power on the RHS.
| _pdp_ wrote:
| 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.
| tomerv wrote:
| This article is about planar graphs, which aren't really
| related to knowledge graphs.
| [deleted]
| throwaway81523 wrote:
| (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.
| monic wrote:
| Fully dynamic planarity testing in polylogarithmic time
|
| https://arxiv.org/abs/1911.03449
|
| https://www.youtube.com/watch?v=1deOVlruc-o
| phaemon wrote:
| 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.
| js8 wrote:
| > 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.
| xcambar wrote:
| 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.
| ffhhj wrote:
| Can imagine Logo programming lang for graphs.
| thomasahle wrote:
| 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.
| lostmsu wrote:
| What are some practical uses for an algorithm like that?
| asimpletune wrote:
| To find short circuits of a theoretical chip. Basically any
| time you want to know if wires get crossed.
| tromp wrote:
| 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 wrote:
| How? But, yeah, for large graphs it should be (somewhat)
| faster.
| [deleted]
| goldenkey wrote:
| 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...
___________________________________________________________________
(page generated 2021-05-26 23:00 UTC)