snippetMinor
Algorithm to generate all planar graphs
Viewed 0 times
allgraphsplanaralgorithmgenerate
Problem
Is there an algorithm which provides a sequence of all simple planar graphs, unique by graph isomorphism? For instance: first all planar graphs with 1 node, then all planar graphs with 2 nodes, etc.
Note: It is okay if it generates only graphs with a minimal node degree of 1 or 2.
Note: It is okay if it generates only graphs with a minimal node degree of 1 or 2.
Solution
One approach would be to enumerate all graphs of a given size, then test each one to see if it is planar and filter out the non-planar ones. This might work acceptably if you only want very small graphs.
Brendan McKay has a collection that enumerates all non-isomorphic planar graphs of size up to 11, which you could download and use directly. There are about 16 million different planar graphs of size up to 11, so if you're lucky you might not need to consider anything larger and that collection will be adequate.
Brendan McKay has a collection that enumerates all non-isomorphic planar graphs of size up to 11, which you could download and use directly. There are about 16 million different planar graphs of size up to 11, so if you're lucky you might not need to consider anything larger and that collection will be adequate.
Context
StackExchange Computer Science Q#39637, answer score: 4
Revisions (0)
No revisions yet.