Lattice , Planar graphs and GraphViz

spx2 has asked for the wisdom of the Perl Monks concerning the following question:

Hi,

I need a module(preferably from CPAN) that will render a graph planar(if possible) or if not reduce to a minimum the edge crossings that occur.

The purpose of this is to make a graph more readable which otherwise(because it has lots of edges) would not be so.

Also, is there any way I could use GraphViz so that I get a lattice(nodes lie on multiple horizontal layers which in turn are stacked on top of one another and on top and bottom layers there is just one node) ?

GraphViz seems to not have support for planar graphs(however,I can drop GraphViz and go for something else if it supports planarity).

Best regards,
Stefan

Comment on Lattice , Planar graphs and GraphViz

Replies are listed 'Best First'.
Re: Lattice , Planar graphs and GraphViz by grizzley (Chaplain) on Oct 15, 2009 at 13:06 UTC
Doesn't GraphViz do it by default? It always tries to reduce crossings. You can probably help by grouping edges into subgraphs if you can "manually" decide which nodes should be together in the neighbourhood.	[reply]
Re^2: Lattice , Planar graphs and GraphViz by spx2 (Deacon) on Oct 15, 2009 at 14:42 UTC
after I group nodes into subgraphs can I still plot the subgraphs as one big graph ? I guess you mean to cluster the nodes, no ?	[reply]
Re^3: Lattice , Planar graphs and GraphViz by grizzley (Chaplain) on Oct 16, 2009 at 08:04 UTC
Yes, cluster nodes. And yes, subgraphs will be part of one graph. And it will probably do what you want (connecting nodes). I wanted the opposite - connect borders of subgraphs and it was very tricky. If you work on Windows then you will have many graphviz examples in directory `C:\Program Files\Graphviz2.22\share\graphviz\graphs`, e.g. `C:\Program Files\Graphviz2.22\share\graphviz\graphs\directed\clust2.gv` which show well how graphviz (well, actually dot, not graphviz: `dot.exe -Tpng clust2.gv > clust2.gv.png`) renders it.	[reply] [d/l] [select]
Re: Lattice , Planar graphs and GraphViz by blokhead (Monsignor) on Oct 15, 2009 at 15:27 UTC
Yes, in Graphviz you can connect up many subgraphs. Keep in mind that computing the minimum crossing number of a graph is NP-hard (although checking for planarity can be done efficiently). So it is a pretty tough thing to ask of a graph layout engine. Graphviz (and probably any other layout engine) uses only heuristics in its layout. You may want to check out the Boost graph library. It does appear to have Perl bindings, though I can't speak from any personal experience. It is not clear whether the Perl bindings can do everything the C++ bindings can do. But it is clear that Boost is more of a graph theory library than Graphviz, and it seems able to do some really nice things, including drawing a planar embedding (see this example). If you give it a try, I'd be interested in hearing how it works. blokhead	[reply]