8
$\begingroup$

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

GridGraph

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:

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

Delaunay triangulation of points

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

Improve this question
$\endgroup$
7
  • $\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$
    – István Zachar
    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

Reset to default
11
$\begingroup$

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[2];
pts2d = RandomReal[10, {10, 2}];
pointsToGraph[pts2d, Graph]

Mathematica graphics

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

Mathematica graphics

Improve this answer
$\endgroup$
8
$\begingroup$

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]

enter image description here

Improve this answer
$\endgroup$
1
  • $\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
6
$\begingroup$

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

Graphics`Mesh`MeshInit[];
dt = Delaunay[pts];

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

Delaunay graph from randomly chosen points

Compare:

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

Delaunay triangles

Improve this answer
$\endgroup$
2
$\begingroup$

With IGraph/M,

pts = RandomPoint[Disk[], 10];

IGMeshGraph@DelaunayMesh[pts]

enter image description here

Improve this answer
$\endgroup$

Your Answer

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

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