Connectivity Optimization / Untangling Planar Graphs

About a month ago Mattias asked a question about finding layouts of a set of nodes connected by lines that don't produce crossings:

http://www.grasshopper3d.com/forum/topics/connectivity-optimization

That thread lead to some interesting discussion of force-directed-graphs, but not really any answer to the original question. It stuck in my mind though...

So when I was reading Terry Tao's blog this morning and was lead to this nice little mathematical game I was reminded of it.

The game quickly gets pretty challenging - and is quite reminiscent of the process of trying to rearrange a grasshopper definition to make it more readable.(and maybe it's good training for that!)

Browsing around some of the material linked to on that page lead to a few interesting mathematical papers on the subject:

Moving Vertices to make drawings plane

Untangling Polygons and Graphs

Untangling a Planar Graph

Though I haven't studied them too deeply yet, some of them seem to contain promising approaches for automating solutions to this problem:

(a figure from the 3rd paper linked to above)

I think Mathias's original question was about using untangled graphs in the actual product of the design, but I guess they could also be really useful to apply to the grasshopper definition itself.

Imagine something like this (maybe combined with a springs/repulsion force-directed approach) that could automatically rearrange your definition to be more readable.

Replies to This Discussion

Permalink Reply by Giulio Piacentino on May 2, 2010 at 10:59am

Hi Daniel, that would be fun! But what should the algorithm do when encountering forbidden graphs?

Permalink Reply by Daniel Piker on May 2, 2010 at 1:07pm

Good question!
Those ones can't be done.
I just learned that if a graph doesn't contain either of these 2 (K5 and K3,3) (or a subdivision of them), then it can always be drawn without crossings. (Kuratowski's theorem)

I guess also that absence of crossings is not really the only thing that makes a graph subjectively readable. In fact a lot of the time arrangements with some crossings are preferable. The left-right flow is pretty important too.
I wonder how clearly we can define the characteristics of a good/clear arrangement for a gh definition ?

RSS