7 - Counting planar graphs and related families of graphs

Summary

Abstract

In this article we survey recent results on the asymptotic enumeration of planar graphs and, more generally, graphs embeddable in a fixed surface and graphs defined in terms of excluded minors. We also discuss in detail properties of random planar graphs, such as the number of edges, the degree distribution or the size of the largest k-connected component. Most of the results we present use generating functions and analytic tools.

Introduction

We consider planar graphs as combinatorial objects, regardless of how many different embeddings they may have in the plane. Let g_n be the number of labelled planar graphs with n vertices, and let R_n be a graph taken uniformly at random among all g_n labelled planar graphs with n vertices. The main questions we are interested in are the following.

1. (1) How large is g_n asymptotically?

2. (2) Which are the typical properties of R_n for n large?

3. (3) What can be said about related families of graphs?

As we are going to see, we have a complete answer to question (1), and significant results concerning (2) and (3). A precise estimate for g_n was obtained by the present authors [38], together with the derivation of limit laws for the basic parameters in random planar graphs. The techniques introduced in [38] have been applied to the analysis of other classes of graphs [12, 35], to the analysis of more advanced parameters [24, 25, 39], and to the uniform sampling of planar graphs [30].