Kyoto Prize Laureate Unsnarls Electronic Networks 36
An anonymous reader writes "Electronic networks — from wireless cellular to the Internet — are often too big to simulate node-by-node, but new uses of graph theory are unsnarling them, according to former Microsoft Research fellow and electronics-guru Laszlo Lovasz, who spoke at the Kyoto Prize Symposium this week. 'We are identifying what is common to these networks—mathematically—so that even very large networks can be accurately modeled,' said Lovasz. He also showed some very cool methods that anybody can use to make any network--even simple organizational charts--easier to read. And even if you don't use them for real work, they are just fun to play with (his app, for instance, allows you to input a random network, which it then redraws right before your eyes so no connections cross over each other, making them extremely legible)."
Auto-ordering graphs? yed has done this for years. (Score:5, Informative)
As the subject says: yed [yworks.com] does not only allow you to lay the connections (I don't like the term "edges". It's counter-intuitive to me.) so that they do not cross
It allows you do set a buttload of parameters and use different algorithms like organic, hierarchical, orthogonal, circle, tree for the nodes and the connections. You can even make it change the laying of connections separately.
It's a fairly mature program too.
Re:"so no connections cross over each other" (Score:4, Informative)
There is something wrong with the summary. An elementary result of graph theory is that some graphs are not planar, [wikipedia.org] i.e. that some graphs cannot be drawn in a plane without any edges crossing.
The app's a little beside the point (Score:5, Informative)
After all, it deals with a graph whose nodes and connections are already known exactly.
The more interesting part comes when you move to a graph like the link structure or underlying router structure of the internet, which is both orders of magnitude larger and changing rapidly -- even if you could take a perfect snapshot of it, by the time you finished analyzing that snapshot the network would have changed quite a bit in the meantime.
What Lovasz has been doing recently with his work on "graph limits" is providing a framework for analyzing such graphs. You can imagine global properties of the network approaching some sort of fixed equilibrium and hope to analyze that equilibrium without actually knowing the details of how the network is changing. I don't actually know if the work has been used in practical applications yet, but the concept goes far beyond just redrawing planar graphs.
Re:Auto-ordering graphs? yed has done this for yea (Score:4, Informative)
Now we only need (Score:5, Informative)
Re:10 years late is cutting edge at MS (Score:4, Informative)
dot,dotty (now graphvis) beats that by another 10 years....
Re:asda (Score:2, Informative)
TFA is not all that useful in actually mentioning what this guy did. It only mentions Lovazs' local lemma (a way to create existential proofs, which is a proof that something exists that does not show the thing whose existence it proves).
Lovasz on wikipedia [wikipedia.org]
And the guy has an Erdos number of 1, so he's probably a good mathematician.
Existential proofs are sometimes frustrating things as they do not answer the obvious question "well it exists, so what the bloody hell is it ?". Sometimes hundreds of year pass between the finding of an existential proof and a constructive one, meaning that constructive math is generally perceived to be more limited in scope than non-constructive mathematics. But this has not been proven, and over the years constructivist math has sometimes caught up, sometimes lost ground. An example is that there has been long disagreement between constructivist and non-constructivists about whether the square root of 2 existed. An existential proof of irrationality is easy to come by, in dozens of versions, and only much later it became known how to represent the actual number.
Re:Graphviz (Score:5, Informative)
I wonder where we can take a look at this app. Anybody know?
You can find yEd at http://www.yworks.com./ [www.yworks.com] You can find Graphviz at http://www.graphviz.org./ [www.graphviz.org]