4
$\begingroup$

I need to create all possible connected and directed graphs with N vertices. The graphs are Planar and labelled with vertices 1 to N. Although the graphs are unweighted, the graphs are non simple since they are directed. Isomorphic graphs must be discarded. We must consider the following characteristics:

  1. Vertex 1 has one connected edge (degree=1), and direction: from vertex1 to vertex2
  2. Vertex N has one connected edge (degree=1), and direction: from vertex(N-1) to vertexN
  3. All other vertices must have degree=3 (three conected edges), with at least one edge entering and one edge going out of the vertex.
  4. Vertex1 always connect to vertex2. Direction: vertex1-->vertex2
  5. Vertex(N-1) always connect to vertexN. Direction: vertex(N-1)-->vertexN

How can I do it efficiently?

And How can I save each graph separately for individual use afterwards?

$\endgroup$
  • $\begingroup$ Welcome to Mathematica.SE! Is the question about Mathematica, the software or should we move the question over to Mathematics? $\endgroup$ – Johu Sep 18 '18 at 20:58
  • $\begingroup$ What have you tried? $\endgroup$ – David G. Stork Sep 18 '18 at 21:40
  • 2
    $\begingroup$ Please clarify the question. The title says random graphs, but there is no mention of this in the question. The title mentions planar, the body doesn't. Are the graphs labelled or not? Does vertex 1 always connect to vertex 2 (and not vertex 3), or do you just mean that it's out-degree is 1? Voting to close the question until it is made to be clear and unambiguous. $\endgroup$ – Szabolcs Sep 19 '18 at 7:55
  • 1
    $\begingroup$ @Szabolcs I think this is an interesting question to tackle, but it definitely requires more stringent definition of the problem at hand. Are non-simple graphs allowed? Is uniform sampling required, and how about graph isomorphisms in that case? Is enumerating all graphs a good alternative as a solution? (Well, that wouldn't probably work for more than the smallest graphs...) $\endgroup$ – kirma Sep 19 '18 at 15:05
  • 2
    $\begingroup$ I vote for leaving it closed, as the questions raised by Szabolcs are not addressed. It makes a huge difference, if it is required, that the graph is planar. $\endgroup$ – Johu Sep 19 '18 at 15:29
4
$\begingroup$

For the easier case of generating a random undirected planar graph with given degree distribution, you can generate a random graph with the desired degree distribution using DegreeGraphDistribution until you get a PlanarGraph:

rpg[n_] := Module[{g}, Quiet[While[Not @ PlanarGraphQ[
   g = RandomGraph[DegreeGraphDistribution[Flatten[{1, ConstantArray[3, n - 2], 1}], 
     SelfLoops -> False]]]]; 
  PlanarGraph[Range @ n, EdgeList @ g]]] 

Examples:

n = 6;
Grid[Partition[Table[With[{g = rpg[n] }, SetProperty[g, {ImageSize -> 300, 
  GraphStyle -> "VintageDiagram",  EdgeShapeFunction -> "CurvedArc", 
  PlotLabel -> VertexDegree[g]} ]], 6], 3]]

enter image description here

n = 8;

enter image description here

n = 10;

enter image description here

n = 12;

enter image description here

TODO: Process the EdgeList or the AdjacencyMatrix of rpg[n] to get the desired configuration of edge directions.

$\endgroup$
2
$\begingroup$

It won't necessarily have all the properties you desire, but this will get you a directed connected planar graph:

pts = RandomReal[{-1, 1}, {25, 2}];
myR = DelaunayMesh[pts]; 

Extract the point adjacencies:

   mycells =( MeshCells[myR, 1] /. Line[n_] -> n)

Get connection rules:

therules = (Rule[#[[1]] , #[[2]]] & /@ mycells)

Create the graph

Graph[therules]

enter image description here

Confirm:

PlanarGraphQ[%]

(* True *)

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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