Generating Graphs Uniformly at Random

Generating Graphs Uniformly at Random. This paper deals with the problem of sampling from a uniform distribution on various classes of graphs of given size. We consider algorithms and restarting procedures for uniform generation of several kinds of trees, arbitrary unlabelled graphs and various kinds of labelled graphs. Most of the material discussed in this paper has been developed during the last decade by several authors. In section 4.3 some recent results on the generation of outerplanar graphs and maximal planar graphs are presented.AMSSubject Classification: 05C.