[Date Index] [Thread Index] [Author Index]

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