Random Planar Graphs
The Gnp model of random graphs, introduced by Erdös and Renyi in the 60's, has led to numerous beautiful and deep theorems. A key feature that is used in basically all proofs is that edges in Gnp appear independently. This situation changes dramatically if one considers graph classes with structural side constraints. For example, in a random planar graph Rn (a graph drawn uniformly at random from the class of all labelled planar graphs on n vertices) the edges are obviously far from being independent. In this talk we survey progress on the study of properties of random planar graphs and the methods that were used and developed in order to achieve this progress.
Angelika Steger, Institute of Theoretical Computer Science, ETH Zürich, Switzerland
