# ICS 269, Spring 1997: Theory Seminar

## 2 May 1997:

Non-Isomorphic Graph Generation

Brad Hutchings, ICS, UC Irvine

Time and space efficient non-isomorphic graph generation may have
applications in graph compression, generating graph catalogs, and
computationally looking at properties of sets of graphs. Brendan McKay's paper *
Isomorph-Free Exhaustive Generation* presents an abstract
framework that can be applied to many interesting graph and
non-graph generation problems. I will discuss two graph generation
problems, Maximal Planar Graphs and Triangle Free Graphs. I will
then explain how McKay's general method applies to graph problems
and compare with selected graph generation schemes.