Random Graphs from Classes with Constraints

random from graph classes with structural constraints, like for
example planar graphs. In particular, denote for a graph G by b(s; G)
the number of blocks (i.e. maximal biconnected subgraphs) of G
that contain exactly s vertices, and let lb(G) be the number of
vertices in the largest block of G. We show that under certain
natural and easy to verify assumptions on the graph class under
consideration, there are only two ways how a random graph with n
vertices looks like with high probability:

I) lb(G) < log n
II) lb(G) = cn for some c depending on the graph class, an the
second largest block contains n^a vertices, where a < 1.

Random planar graphs are of type (II), while for example K_4-
minor free graphs are of type (I). We will discuss some implications
of this results towards a random graph theory for constrained graph
classes, and talk about the major remaining challenges.