Hans Jürgen Prömel -Humboldt-Universität Berlin

On random planar graphs

Abstract: The classical theory of random graphs contains many results on properties that a graph, chosen uniformly at random from the set of all graphs, satisfies with high probability.

However, much less is known about random graphs which are chosen from graph classes defined via some side-constraints. In this talk we will study results and techniques used to investigate random planar graphs.

Among other topics, we will give lower and upper bounds on the typical number of edges of a random planar graphs, as well as discuss connectivity, degrees and chromatic number. The methods that we shall use and explain are based on markov chains and asymptotic counting.

Colloquium - 16 Uhr s.t.

Dirk Schlatter-Humboldt Universität zu Berlin

On Maximum Planar Subgraphs of Random Graphs

Abstract: The Maximum planar subgraph problem consists of finding a spanning planar subgraph with a maximum number of edges in a given graph. We investigate this question for random graphs and try to determine the threshold function such that G(n,p) contains a planar subgraph H with m=rn edges.

We shall prove that it can be bounded between n^{(-1/r)} and n^{(-1/r + d)}, where d is an arbitrarily small positive constant. In the cases of m=2n-4 and m=3n-6, we will present a simple and efficient algorithm for finding H, and, answering a question by Bollobas and Frieze, we can determine the precise threshold.