# How to create a planar graph from a set of random points

Question

Given a set of points in the plane, how can you create a planar graph in the standard graph representation of Mathematica (version 9 or higher), from these points?

Background

A planar graph is a graph embedded in the plane in such a way that the edges intersect at vertices only. 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.

• 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

In Version 10, we can do this nicely even for 3D point sets:

pointsToGraph[pts_, graph : (Graph | Graph3D)] :=
Module[{del = DelaunayMesh[pts], edges},
edges = UndirectedEdge @@@ MeshCells[del, 1][[All, 1]];
graph[Range@Length@pts, edges, VertexLabels -> "Name", VertexCoordinates -> pts]
]

SeedRandom;
pts2d = RandomReal[10, {10, 2}];
pointsToGraph[pts2d, Graph] SeedRandom;
pts3d = RandomReal[10, {30, 3}];
pointsToGraph[pts3d, Graph3D] 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 With IGraph/M,

pts = RandomPoint[Disk[], 10];

IGMeshGraph@DelaunayMesh[pts]
` 