Calculate all possible connected planar graphs with "E" edge
I'm developing a c++ program which calculate and draw all possible connected planar graphs with given E number edge. Like this :
My first thought was to find all possible solutions for the N edge by adding one edge to after finding the answer to (n-1) by doing recursion.
As you can see in the picture, the solution of the problem n = 4 is basically an improved version of the solution n = 3 with one edge more.
But it did not feel like a very effective solution. I could not find this problem in a particular algorithm.
is there any other way of finding and drawing all possible connected planar graphs with E edge?
is there any other way of finding and drawing all possible connected planar graphs with E edge?
Start with the complete graph K(E+1) - this will have (E+1) vertices and E(E+1)/2 edges. Enumerate the edges 1 .. E(E+1)/2.
- For each permutation of
Evalues from the set<1 .. E(E+1)/2>- Keep those
Eedges and delete the rest - Delete any unconnected vertices
- If the graph is connected, planar and is not isomorphic to a previous graph then
- It is a new unique graph with E edges.
- Keep those
You can probably perform significant optimisations by considering the symmetry of the complete graph and eliminating permutations that have a combination of rotational and/or reflectional symmetry with a previous permutation.
- Constructing a tree data structure recursively, from an array of strings that maintain an order of precedence
- Delete node at nth position from doubly linked list recursively? (C++)
- How should I convert this recursive function into iteration?
- best way to find Fibonacci number
- Will this be a tail call or not?
- Calculating a catalan number in C
- Tail Call Optimisation in Java
- How to correctly loop in GAMS models with dynamics in equations?
- Why this recursion example in ocaml doesn't work for negative number?
- OCaml higher order functions
- Tail-recursively, maximum element in a binary tree in OCaml
- Tail-Recursive Binomial Coefficient Function in Java
- Jinja templating with recursive in dict doesn't works
- The output of the tree to a string
- How do I know if a function is tail recursive in F#
- How can I render a component in its own component (recursively) in svelte?
- what is the output of this simple recursive function? can you explain in detail?
- Using a recursive method to determine if a word is elf-ish
- How does regular expression engine parse regex with recursive subpatterns to match palindromes?
- "Backwards recursive" query in PostgreSQL?
- Storing the recursive call result in a variable leads to incorrect calculation in a DP memoized solution
- How to print odd numbers using recursive java with the limits = n
- gcc complains for infinite recursion while freeing binary tree
- generating list satisfying linear integer constraint in python
- C# Dictionary recursion
- Find full path of element in tree
- How about the recursive code for "Find Zero" I've written?
- deleting duplicates tail recursively in OCaml
- Does recursive call have to be strictly the last call in a function for a function to be tail-recursive?
- Struggling to build an ascending and alternating recursive function identifier in C