plantri and fullgen

plantri and fullgen are programs for generation of certain types of planar graph.

The authors are Gunnar Brinkmann (University of Ghent) and Brendan McKay (Australian National University).

Graphs are generated in such a way that exactly one member of each isomorphism class is output without the need for storing them. The speed of generation is more than 100,000 graphs per second in most cases, so extremely large classes of graph can be exhaustively listed.

plantri [November 30, 2001]

The graph classes generated by plantri include:

• Planar triangulations
  • connectivity 1, 2, 3, 4 or 5
  • minimum degree 3, 4 or 5
  • eulerian with connectivity 3 or 4
• Planar quadrangulations
  • arbitrary simple
  • 3-connected
  • minimum degree 3 and simple
  • 3-connected, no non-facial 4-cycles
• Planar simple graphs
  • connectivity 1, 2 or 3
  • minimum degree 1, 2, 3, 4 or 5
• Triangulations of a disk
  • connectivity 2 or 3
  • minimum degree 2 or 3
• Planar cubic graphs
  • connectivity 1, 2, or 3
  • connectivity 1, 2, or 3
  • girth 3, 4 or 5
  • cyclic connectivity 3, 4 or 5
  • bipartite with cyclic connectivity 3 or 4
• Planar quartic graphs
  • 3-connected simple
  • 4-edge-connected simple
  • 4-edge-connected
  • 3-connected, 6-cyclically-edge-connected

For more details, see the manual.

fullgen

The program fullgen generates fullerenes, which are planar cubic graphs having only faces of size 5 or 6.

There is also an option for forbidding adjacent pentagons.

For more details, see the manual.

The update of Jan 10, 2004 uses "long long" type to prevent some values from overflowing. The fullerenes themselves were already ok but for very large sizes the wrong counts might have been reported. One wrong count (for 174 vertices) was also corrected in the manual.

Download the programs

The programs are written in C and are free for all purposes other than sale for profit. However, they remain subject to our copyright and are not "public domain".

They should compile with any modern C compiler and do not need any special libraries. However, they are mostly tested under UNIX.

plantri and fullgen are distributed together as a gzipped tar file (Version 4.1).

Version 3.0 had a bug you did not encounter. See the change log for details.

Related papers

G. Brinkmann and B. D. McKay, Fast generation of planar graphs (expanded edition): PDF file.

G. Brinkmann, S. Greenberg, C. Greenhill, B. D. McKay, R. Thomas and P. Wollan, Generation of simple quadrangulations of the sphere: PDF file. (Discrete Mathematics, 305 (2005) 33-54).

G. Brinkmann and B. D. McKay, Construction of planar triangulations with minimum degree 5: PDF file. (Discrete Mathematics, 301 (2005) 147-163.)

Related programs

Contact the authors

Gunnar Brinkmann: gunnar@mathematik.uni-bielefeld.de
Brendan McKay: bdm@cs.anu.edu.au    http://cs.anu.edu.au/~bdm