Re: How to layout a planar graph so that it doesn't have any intersecting edges?
- To: mathgroup at smc.vnet.net
- Subject: [mg125008] Re: How to layout a planar graph so that it doesn't have any intersecting edges?
- From: David Bailey <dave at removedbailey.co.uk>
- Date: Fri, 17 Feb 2012 06:27:02 -0500 (EST)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
On 16/02/2012 08:29, Szabolcs Horv=E1t wrote: > A planar graph is a graph that can be drawn in the plane so that no > two edges will intersect. > > Combinatorica`PlanarQ will test if a graph is planar. > > My question is: How can we draw a graph that is known to be planar > without intersecting edges in Mathematica? Is there a function / > method for this? > > --------8<--------- > > I posted the same question here as well: > > http://mathematica.stackexchange.com/q/1781/12 > > At the time when I'm writing this, there are no answers, but please > check that thread when you read this, in case any progress has been > made on the problem. > > -------->8-------- > > For testing, here's some code which will randomly generate a number of > small planar graphs. All of these should be drawn without > intersecting edges by the method (they are not drawn like this by the > default layout algorithm) > > << ComputationalGeometry` > > graphs == DeleteDuplicates[ > Flatten@Table[ > Graph@ > Union[Sort /@ > Join @@ (Thread /@ > DelaunayTriangulation@RandomReal[1, {j, 2}])], > {25}, {j, 4, 12} > ], IsomorphicGraphQ]; > At version 8, there is a Graph construct that takes various options to control its layout. I don't know if there is a method that is guaranteed to layout a graph in planar form if that is possible, but certainly that is what you usually get. I would definitely start from the new Graph primitive. David Bailey http://www.dbaileyconsultancy.co.uk