×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Kyoto Prize Laureate Unsnarls Electronic Networks

timothy posted about 3 years ago | from the topology-with-a-purpose dept.

Communications 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)."

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

36 comments

"so no connections cross over each other" (1)

SquirrelDeth (1972694) | about 3 years ago | (#35765116)

Never cross streams dudes.

Re:"so no connections cross over each other" (4, Informative)

Anonymous Coward | about 3 years ago | (#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:"so no connections cross over each other" (1)

degeneratemonkey (1405019) | about 3 years ago | (#35765584)

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:"so no connections cross over each other" (2)

Zerth (26112) | about 3 years ago | (#35765874)

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

Re:"so no connections cross over each other" (1)

Jurily (900488) | about 3 years ago | (#35767522)

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.

Re:"so no connections cross over each other" (0)

Anonymous Coward | about 3 years ago | (#35768246)

Yes, but for those that are... it's a gplanarity bot!

asda (0)

Anonymous Coward | about 3 years ago | (#35765120)

> (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)."

Isn't that kind of thing ANCIENT? Decades old?

Re:asda (2)

pjt33 (739471) | about 3 years ago | (#35766068)

I know Tarjan published a paper on it in the 70s because I once tried to implement it.

Re:asda (3, Informative)

OeLeWaPpErKe (412765) | about 3 years ago | (#35766378)

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:asda (2)

gilleain (1310105) | about 3 years ago | (#35766482)

I know Tarjan published a paper on it in the 70s because I once tried to implement it.

He did (Hopcroft and Tarjan, 1973). There are some more recent approaches, too. I've read, and should try implementing, one by Boyer and Myrvold (2004). I really suffer from "not-invented-here" syndrome as I know of at least one implementation in the language I want it in :)

Re:asda (2)

gilleain (1310105) | about 3 years ago | (#35766488)

Ha! Also, on actually RTFA, I notice that the link to the "rubber band" software is called "Tutte.zip" - presumably it is this Tutte [wikipedia.org]. I think it involves fixing a cycle of the graph as an outer face, and applying a kind of simulated annealing (optimisation) approach to layout the other vertices.

Auto-ordering graphs? yed has done this for years. (5, Informative)

Anonymous Coward | about 3 years ago | (#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 (4, Informative)

Anonymous Coward | about 3 years ago | (#35765252)

Another great piece of graphing software: Cytoscape [cytoscape.org].

10 years late is cutting edge at MS (1)

emeade (123253) | about 3 years ago | (#35765320)

CASE tools could untangle graphs in 1999.

Re:10 years late is cutting edge at MS (3, Informative)

mevets (322601) | about 3 years ago | (#35765736)

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

The armchair QB big talker spouting drivel again? (0)

Anonymous Coward | about 3 years ago | (#35801480)

Man, shut the hell up already you big talking goof. You're not amusing and you offer zero valid advisement in any and all of your posts. Please, don't waste our time on this forums anymore with your drivel.

Re:Auto-ordering graphs? yed has done this for yea (1)

tgv (254536) | about 3 years ago | (#35765936)

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

Killer app for this tech (1)

Yoik (955095) | about 3 years ago | (#35765164)

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

Lovasz is better know for his mathematics... (3, Interesting)

Anonymous Coward | about 3 years ago | (#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...

nobel math; how many versions of the truth (-1, Offtopic)

Anonymous Coward | about 3 years ago | (#35765186)

child's play. untangling what we're issued? one would need all of the deities (books banners weird symbols etc...) & extreme unction just to get a good paying position in the gallery?

having shopped for centuries, the genuine native american elders rising bird of prey leadership initiative (teepeeleakes etchings), makes our measurably unholy history (terror alert .5b pop.; no survivors, no history, exit (stage another alert) strategy) so clear to us, that the future cannot help but be brighter.

Re:nobel math; how many versions of the truth (1)

Anonymous Coward | about 3 years ago | (#35765390)

The genuine Native-American elders' rising Bird-of-Prey leadership initiative (Teepeeleakes Etchings)

Brilliant prose. Who knew, the native Indians were the inspiration for the Wikileaks organization.

The app's a little beside the point (4, Informative)

kevinatilusa (620125) | about 3 years ago | (#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.

Re:The app's a little beside the point (0)

Anonymous Coward | about 3 years ago | (#35765990)

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.

Check out the P2P connections in Vuze sometime. :)

Could that be applied to our brain? (-1, Troll)

thefun (2037176) | about 3 years ago | (#35765210)

After all, it is one big graph of logical gates... And maybe that will help with reverse-enginerring [tinyurl.com] of hardware chips... That is essential to fight the hardware based DRM

Re:Could that be applied to our brain? (0)

Anonymous Coward | about 3 years ago | (#35765250)

Goatse Alert!

Graphviz (0)

Anonymous Coward | about 3 years ago | (#35765376)

I wonder how graphviz's algorithms stand up in comparison and whether it could benefit from this work.

Well it sounds like ok stuff (4, Interesting)

Anonymous Coward | about 3 years ago | (#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!

great (0)

Anonymous Coward | about 3 years ago | (#35766128)

Now we need something that can make the history tree of operating systems legible.

Autoroute? (0)

Anonymous Coward | about 3 years ago | (#35766496)

"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"

Sounds like what autoroute does when you're laying out a PCB.

coachregion (-1, Offtopic)

tonnyben (2022156) | about 3 years ago | (#35766588)

[url=http://www.coachregion.com]coach leather handbags[/url] [url=http://www.coachregion.com]coach shoulder bags[/url] [url=http://www.coachregion.com]coach purses[/url] [url=http://www.coachregion.com]coach handbags[/url] coach leather handbags [coachregion.com], coach shoulder bags [coachregion.com], coach purses [coachregion.com], coach handbags [coachregion.com], coach leather handbags [coachregion.com] coach shoulder bags [coachregion.com] coach purses [coachregion.com] coach handbags [coachregion.com] coach leather handbags [coachregion.com] coach shoulder bags [coachregion.com] coach handbags [coachregion.com] coach backpacks [coachregion.com] coach luggage bags [coachregion.com] coach sling bags [coachregion.com] coach business bags [coachregion.com] http://www.coachregion.com/ [coachregion.com] our email:coachregion@live.com

monster beats (-1, Offtopic)

beats headphone (2037600) | about 3 years ago | (#35768132)

i bought the monster beats [special-be...dphone.com] headphone almost 1 year and feel good, they have amazing clarity and bass. Once you have heard a song from these headphones, the other headphones will seem no good.and mainly the things:good: The Monster beats by dre [special-be...dphone.com] headphones have a stylish . comfortable design as well as exceptionally crisp audio response. Sound quality , balanced, warm mids and thumping bass. also Included are a great carrying box and a music-phone-compatible cable. cool and Striking but cannot be used without batteries.

this is the site i bought, www.special-beats-headphone.com/ and the most importent is the attractive price, hope it helps you .

Check for New Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...