Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

up vote 6 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
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}]];

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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