# Create a planar graph from a set of random points

A planar graph is a graph embedded in the plane in such a way that the edges intersect at vertices. This is an example of a planar graph:

g = GridGraph[{3, 3}]


It is stored in the standard Mathematica representation for graphs.

You can also draw a planar graph from a set of points in the plane with ComputationalGeometryPlanarGraphPlot:

Needs["ComputationalGeometry"]
pts = RandomReal[{0, 10}, {10, 2}]
PlanarGraphPlot[pts]


However, the output is not in the standard representation for graphs. My question is: given a set of points, how can you create a planar graph in the standard graph representation of Mathematica (version 9)?

-
Hi sjdh - now that I re-read your question, I think I misunderstood what you are looking for. Can you clarify, perhaps a small example of what the input/output should be? –  bill s Apr 6 '13 at 11:17
@sjdh You basically want to be able to draw a planar graph with the new Graph objects instead of the old graph methods used in Mathematica 7? –  Lou Apr 6 '13 at 11:36
I've edited your question, please check if I got your intention correctly. Feel free to roll back if not. –  István Zachar Apr 6 '13 at 12:00
@IstvánZachar You've got my intention. Thank you for your edit. –  sjdh Apr 6 '13 at 12:06
@bills Using the words of IstvánZachar, I like to "build a graph by collecting all the edges of a Delaunay triangulation" –  sjdh Apr 6 '13 at 12:11

Using Mark McClure's answer, one can easily build a graph by collecting all the edges of a Delaunay triangulation and then removing duplicates. For non-crossing layout, use GraphLayout -> "PlanarEmbedding" (since v9) and add the original points as vertex coordinates.

Needs["ComputationalGeometry"];
pts = RandomReal[{0, 10}, {10, 2}];
dt = DelaunayTriangulation[pts];
toPairs[{m_, ns_List}] := Map[{m, #} &, ns];
edges = Union[Sort /@ Flatten[toPairs /@ dt, 1]];
Graph[edges, VertexLabels -> "Name", ImagePadding -> 20,
GraphLayout -> "PlanarEmbedding", VertexCoordinates -> pts]


-
In your example, some edges cross each other. I would like a result in which non of the edges cross. I'll add this to my question. –  sjdh Apr 6 '13 at 12:17

Here's one possibility, using an undocumented function for the Delaunay triangulation:

BlockRandom[SeedRandom[131, Method -> "MKL"]; (* for reproducibility *)
pts = RandomReal[{0, 10}, {10, 2}]];

GraphicsMeshMeshInit[];
dt = Delaunay[pts];

Graph[Range[Length[pts]], UndirectedEdge @@@ dt["Edges"], VertexCoordinates -> pts]


Compare:

GraphicsComplex[dt["Coordinates"],
{FaceForm[None], EdgeForm[Black], Polygon[dt["Faces"]]}] // Graphics
`

-