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

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

• To: mathgroup at smc.vnet.net
• Subject: [mg124990] How to layout a planar graph so that it doesn't have any intersecting edges?
• From: Szabolcs HorvÃt <szhorvat at gmail.com>
• Date: Thu, 16 Feb 2012 03:28:28 -0500 (EST)
• Delivered-to: l-mathgroup@mail-archive0.wolfram.com

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];