6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

House of Graphs is a good resource. From the database, you can download all planar graphs up to 11 vertices.

For generating planar graphs even with some additional properties (e.g. connectivity), have a look at plantri by Brinkmann and McKay.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.