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?


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 ComputationalGeometry`PlanarGraphPlot:

pts = RandomReal[{0, 10}, {10, 2}]

Delaunay triangulation of points

However, the output is not in the standard representation for graphs.

  • $\begingroup$ 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? $\endgroup$
    – bill s
    Apr 6, 2013 at 11:17
  • $\begingroup$ @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? $\endgroup$
    – Lou
    Apr 6, 2013 at 11:36
  • $\begingroup$ I've edited your question, please check if I got your intention correctly. Feel free to roll back if not. $\endgroup$ Apr 6, 2013 at 12:00
  • $\begingroup$ @IstvánZachar You've got my intention. Thank you for your edit. $\endgroup$
    – sjdh
    Apr 6, 2013 at 12:06
  • $\begingroup$ @bills Using the words of IstvánZachar, I like to "build a graph by collecting all the edges of a Delaunay triangulation" $\endgroup$
    – sjdh
    Apr 6, 2013 at 12:11

4 Answers 4


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]

pts2d = RandomReal[10, {10, 2}];
pointsToGraph[pts2d, Graph]

Mathematica graphics

pts3d = RandomReal[10, {30, 3}];
pointsToGraph[pts3d, Graph3D]

Mathematica graphics


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.

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]

enter image description here

  • $\begingroup$ 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. $\endgroup$
    – sjdh
    Apr 6, 2013 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}]];

dt = Delaunay[pts];

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

Delaunay graph from randomly chosen points


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

Delaunay triangles


With IGraph/M,

pts = RandomPoint[Disk[], 10];


enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.