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