6
$\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?

Improve this question
$\endgroup$
18
  • $\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, 2018 at 20:58
  • $\begingroup$ What have you tried? $\endgroup$
    – David G. Stork
    Sep 18, 2018 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, 2018 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, 2018 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, 2018 at 15:29

2 Answers 2

Reset to default
5
$\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.

Improve this answer
$\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 *)

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.