typodupeerror

## Kyoto Prize Laureate Unsnarls Electronic Networks36

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)."
This discussion has been archived. No new comments can be posted.

## Kyoto Prize Laureate Unsnarls Electronic Networks

• #### "so no connections cross over each other" (Score:1)

Never cross streams dudes.
• #### Re:"so no connections cross over each other" (Score:4, Informative)

by Anonymous Coward on Friday April 08, 2011 @10:24PM (#35765176)

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.

• #### Re: (Score:1)

That fact would indeed be relevant if the claim here had anything to do with graphs being drawn in a plane without any edges crossing. Granted, TFS is misleading in this regard; but RTFA.
• #### Re: (Score:3)

Indeed, the sample program even comes with at least one graph that forms a star because it can't be uncrossed.

• #### Re: (Score:2)

An elementary result of graph theory is that some graphs are not planar,

Don't bring math into a discussion about math. This is Slashdot.

• #### Interesting... (Score:2)

in 2008 Laszlo Lovasz was awared the biggest annual award in computer science
• #### Auto-ordering graphs? yed has done this for years. (Score:5, Informative)

by Anonymous Coward on Friday April 08, 2011 @10:21PM (#35765158)

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:Auto-ordering graphs? yed has done this for yea (Score:4, Informative)

by Anonymous Coward on Friday April 08, 2011 @10:47PM (#35765252)
Another great piece of graphing software: Cytoscape [cytoscape.org].
• #### 10 years late is cutting edge at MS (Score:1)

CASE tools could untangle graphs in 1999.

• #### Re:10 years late is cutting edge at MS (Score:4, Informative)

on Saturday April 09, 2011 @01:18AM (#35765736)

dot,dotty (now graphvis) beats that by another 10 years....

• #### Re: (Score:2)

And OmniGraffle does this too, but they most likely all derive their functionality from GraphViz.

• #### Killer app for this tech (Score:1)

I hope someone over at Eve Maps codes this in to make more sense of the galaxy.

• #### Lovasz is better know for his mathematics... (Score:3, Interesting)

by Anonymous Coward on Friday April 08, 2011 @10:24PM (#35765170)

Lovasz is a famous mathematician working in areas of combinatorics at the edge of computer science, but describing him as an "electronics guru" is simply weird...

• #### The app's a little beside the point (Score:5, Informative)

<[moc.liamg] [ta] [lletsock]> on Friday April 08, 2011 @10:27PM (#35765188)

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.

• #### Well it sounds like ok stuff (Score:4, Interesting)

by Anonymous Coward on Friday April 08, 2011 @11:31PM (#35765428)

Before I studied CS (and graph theory) in university, I had gone to college and studied Electronics Engineering for 2 years, then got a job for an electronics design and manufacturing company building industrial control equipment (RTU's, SCADA controllers, magnetic amplifiers (mag amps) for very high power control for petrochemical manufacturers (5000V at 10000 Amps), etc.). One of the bigger problems when laying out a printed circuit board with many chips is where to put the chips so that you have the least number of circuit lines crossing from one side of the board to the other (so as not to short out other lines, etc). Thru holes cost money, and shorter circuit trace lines are more efficient in terms of signal time and current, especially if the fan out of one chip is very close to (but less than) the fan in of another. Some graph theory algorithms are useful for solving this problem, and I wonder if these findings can help make that process faster. Graph Theory: its not just for shortest path ambulance routing, internet packet routing, ship, rail, plane and truck routing, machine tool path efficiency, and shortest set of chemical steps to create medicine anymore!

• #### Now we only need (Score:5, Informative)

on Saturday April 09, 2011 @12:30AM (#35765590)
Single layer PCBs. The free copy of Eagle [cadsoft.de] is much more useful.
• #### Buffer Bloat (Score:2)

Will it simulate buffer bloat [bufferbloat.net] accurately?

Just about every computer on the market today runs Unix, except the Mac (and nobody cares about it). -- Bill Joy 6/21/85

Working...