Research Seminar - May 07, 1999

Abstract

One of the most fundamental activities in graph theory is the construction of catalogues, or lists, of graphs. These catalogues may be quite general (e.g. all graphs on 10 vertices) or more specialised (e.g. all cubic graphs on 20 vertices, or all planar triangulations on 16 vertices). Catalogues such as these may be used directly in searching for examples or counterexamples, or indirectly as a test-bed to develop insight. Therefore there has been significant interest in developing practical algorithms to catalogue graphs (or other combinatorial objects).

One of the main problems in computer generation of catalogues is the isomorphism problem, in that most construction procedures generate many isomorphic copies of each graph. Checking vast lists of graphs for duplicates and eliminating them is an extremely time-consuming and error prone data management problem. An alternative is to devise the construction algorithm in such a way that the isomorphism checking is "built-in" to the algorithm. The ultimate aim of this approach is to devise an orderly algorithm, the output of which is guaranteed to contain precisely one representative of each isomorphism class.

In this talk, I will discuss graph cataloguing, its history and uses, graph construction procedures and orderly algorithms.