Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #8575

Re: How to layout a planar graph so that it doesn't have any intersecting edges?

From David Bailey <dave@removedbailey.co.uk>
Newsgroups comp.soft-sys.math.mathematica
Subject Re: How to layout a planar graph so that it doesn't have any intersecting edges?
Date 2012-02-17 11:29 +0000
Organization Steven M. Christensen and Associates, Inc and MathTensor, Inc.
Message-ID <jhldnm$ov2$1@smc.vnet.net> (permalink)

Show all headers | View raw


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

Back to comp.soft-sys.math.mathematica | Previous | Next | Find similar | Unroll thread


Thread

Re: How to layout a planar graph so that it doesn't have any intersecting edges? David Bailey <dave@removedbailey.co.uk> - 2012-02-17 11:29 +0000

csiph-web