A new algorithm for graph crossings, hiding in plain sight (2020)
quantamagazine.org
A new algorithm for graph crossings, hiding in plain sight (2020)
1–10 of 44 posts
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#2The 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.
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#3Fully dynamic planarity testing in polylogarithmic time
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#4I 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.
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#5The 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.
How? But, yeah, for large graphs it should be (somewhat) faster.
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#6(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.
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#7I 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.
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.
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#8What are some practical uses for an algorithm like that?
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#9I 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.
They can be! I remember when I was about 10, I learned about Eulerian paths from a popular math book for kids.
Re: A new algorithm for graph crossings, hiding in plain sight (2020)
#10What 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.