Graph generators

On this page we provide some links to programs for generating graphs. The list is restricted to free programs and also excludes packages like SageMath. Currently only generators of complete classes of graphs are included, omitting generators of example graphs and random graphs. Graph repositories are not included.

We will be happy to consider other programs if you know of any.

Nauty & Traces

Authors: Brendan McKay and Adolfo Piperno

The nauty package contains many graph generators. The main ones are:

• geng. General graphs, chordal graphs, perfect graphs, split graphs, claw-free graphs, bipartite graphs. Options for minimum and maximum degree, connectivity, presence of 3-cycles, 4-cycles, 5-cycles and K₄. Facility for efficient enforcement of properties preserved by vertex deletion.
• genbg. General bicoloured graphs, many options.
• gentreeg. Trees. Based on code of Gang Li and Frank Ruskey. Options for maximum degree and diameter. Can make forests in conjunction with assembleg.
• gentourng. Tournaments. Options for degree bounds.
• genposetg. Posets (with Gunnar Brinkmann).
• genktreeg. $k$-trees.
• genquarticg. 4-regular graphs (by Narjess Afzaly).
• directg and watercluster2 (with Gunnar Brinkmann). Orient edges of undirected graphs in all distinct ways. Useful for making digraphs. Option for acyclic orientations.
• multig. Add integer weights to edges in all distinct ways. Useful for making multigraphs.
• genspecialg. Lots of special classes of graphs.

Regular graphs

Regular graphs on surfaces will be considered below.

• snarkhunter (Gunnar Brinkmann and Jan Goedgebeur). Cubic graphs with options for girth, colourability and connectivity conditions.
• minibaum (Gunnar Brinkmann). Cubic graphs with girth and bipartite options.
• genquarticg 4-regular graphs, see above.
• genreg (Markus Meringer). Regular graphs of arbitrary degree and girth. A version with more options including bipartiteness is available from Brendan McKay or Gunnar Brinkmann.
• pregraphs (Gunnar Brinkmann and Nico Van Cleemput). General cubic graphs, optionally allowing multiple edges, dangling edges, loops, etc.

Graphs on surfaces

Most available software is for the sphere, but there are exceptions.

• plantri (Gunnar Brinkmann, Brendan McKay and Heidi Van den Camp). Many types of graphs on the sphere: triangulations, quadrangulations, general graphs, bipartite graphs, triangulations of a disk, with lots of degree and connectivity options. CaGe, listed below, includes a version plantri_md6 for triangulations of maximum degree at most 6.
• fullgen (Gunnar Brinkmann). Fullerenes (cubic graphs on the sphere with faces of size 5 and 6, also known as buckyballs).
• buckygen (Jan Goedgebeur). Fullerenes, not all the features of fullgen but generally more efficient.
• qpf (Oliver Heidemeier). 4-regular planar graphs with given face sizes. Ask Gunnar Brinkmann for a copy.
• alternating (Nico Van Cleemput). Alternating plane graphs.
• cgf (Thomas Harmuth). Cubic graphs on surfaces with given faces. Distributed with CaGe, see below.
• surftri (Thom Sulanke). Maps on arbitrary surfaces for which the irreducible triangulations are known.

Graphs of chemical interest

Since a molecule is a graph, many generators have focussed on the types of graph that are chemically relevant. Fullerenes are one case that is mentioned above. We only give a few examples and will not include commercial products.

• CaGe (Gunnar Brinkmann, Olaf Delgado Friedrichs, Sebastien Lisken, Adriaan Peeters and Nico Van Cleemput). This is a program that can generate and visualise a large number of graph types, including hydrocarbons, nanotubes and cones, as well as planar regular graphs and their duals.
• surge (Brendan McKay, Christoph Steinbeck and Mehmet Aziz Yirik). This is a program that generates all the topologies that are possible for a given chemical formula, regardless of their physical plausibility.
• enu (Salomé Rieder, Marina Oliveira, Sereina Riniker and Philippe Hünenberger). Constitutional isomers and stereoisomers of molecular formula.
• nutgen (Kris Coolsaet, Patrick Fowler and Jan Goedgebeur). Nut graphs. These are graphs whose adjacency matrix has a simple zero eigenvalue with an eigenvector which has no zeros.

Miscellaneous

• Combinatorial Object Server (Frank Ruskey, Torsten Mütze, Joe Sawada and Aaron Williams). Simple interface to some of the generators above and also to a plane trees generator.
• gen_hypohamiltonian (Jan Goedgebeur and Carol Zamfirescu). Hypohamiltonian and almost hypohamiltonian graphs.
• critical_Pfree_graphs (Jan Goedgebeur and Oliver Schaudt). Graphs not containing an induced subgraph such as a path or cycle while being critical for $k$-colourability
• generateUHG (Jan Goedgebeur, Barbara Meersman and Carol Zamfirescu). Uniquely hamiltonian graphs and graphs with few hamiltonian cycles.
• triangleramsey (Gunnar Brinkmann, Jan Goedgebeur and Jan-Christoph Schlage-Puchta). Maximal triangle-free graphs and triangle Ramsey graphs.
• ddgraphs (Nico Van Cleemput). Delaney–Dress graphs.
• naumdesign (Brendan McKay). Combinatorial 2-designs. A program is included that can make the incidence graphs and block-insection graphs.
• SAT Modulo Symmetries (Markus Kirchweger, Manfred Scheucher and Tomáš Peitl). A highly extensible graph generator based on SAT solving.

Page Master: Brendan McKay, brendan.mckay@anu.edu.au

Up to the combinatorial data page