The evolution of random graphs on surfaces

For integers g,m≥0 and n>0, let Sg(n,m) denote the graph taken uniformly at random from the set of all graphs on {1,2,…,n} with exactly m=m(n) edges and with genus at most g. We use counting arguments to investigate the components, subgraphs, maximum degree, and largest face size of Sg(n,m), finding that there is often different asymptotic behaviour depending on the ratio mn.