HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

Algorithm to generate all planar graphs

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#39637, answer score: 4

Revisions (0)

No revisions yet.