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