Database of Graphs

[Brendan McKay]

There is a need to distinguish between properties that can be
computed quickly and properties (or graph classes) that are
expensive to compute.

An example of the latter is the class of strongly regular graphs,
and at the current state of technology the best approach is to
store the graphs in a file where they can be examined at will.

On the other hand, easy classes of graphs (all graphs, connected
graphs, graphs without some family of forbidden subgraphs, 
regular graphs, embedded planar graphs, hamiltonian graphs) are
NOT good candidates for storing in a database.  The reason is
that they can be freshly generated at a very fast rate, not
terribly much slower than reading them from a file, and the
number that can be generated is not limited by your disk.
For example, a good graph generator can output a gigabyte of
data every few minutes, and we are still at the point where 1GB
files are regarded as big (especially across the internet).

The correct approach is a suite of programs based on graph 
generators and filters.  It might appear like a database to the
user, but it isn't.  Moreover, it is small so anyone can have it
on their computer without filling their disk.  I've made a small
start in this direction with my "gtools" package, available at
http://cs.anu.edu.au/~bdm/nauty .  So far it doesn't know many
graph properties or graph operations but it is slowly expanding
(often due to requests).  Currently, with help from Paulette Lieby,
I'm busy adding some properties that require sophisticated 
algorithms, such as planarity.  Multigraphs, digraphs, etc will
also be added in due course.  Suggestions are always welcome.

Brendan.


* Jim Nastos <nastos at cs.ualberta.ca> [021201 06:57]:
> On Sat, 30 Nov 2002, Felix Goldberg wrote:
> 
> > Well, there is the "Atlas of Graphs" on paper.  I guess that a
> > sufficiently dedicated team with ample resources could handle the task of
> > translating it into some electronic format.
> 
>   Still, I think there is much use in having 100-or-so properties and 
> which graphs have those properties in a database and being able to 
> intersect properties. The atlas doesn't provide that. A table of graphs 
> that do not contain a certain small induced subgraph would be nice (for 
> each small subgraphs.) Asking for graphs that have no C4 intersect graphs 
> with no C5 intersect graphs with no 2K2 and asking for a common property 
> of these graphs would yield the fact that they are all split graphs, for 
> example, and would give a very strong indication that (C4, C5, 2K2)-free 
> graphs are split (indeed, they are exactly the split graphs.)
>   There are tonnes of graph classes that are still looking for good 
> characterizations (e.g. asteroidal triple-free, weakly chordal graphs is 
> one I've thought a bit about.) The approaches towards AT-free graphs are 
> very different from those used in studying weakly chordal graphs, but 
> their intersection is an interesting class that is still looking for 
> publishable results. A database could provide an excellent initial 
> direction in the investigation. I know I don't want to draw up all these 
> graphs up to 10 vertices and look for common properties...
>   If anyone else out there sees a use in this and is interested in maybe 
> starting to build something useful, let me know. Maybe the integer 
> sequence crowd is not the right one to be asking about this, but I think 
> OEIS could eventually incorporate such functionality.
> 
> Jim Nastos