Asymptotic study of regular planar graphs

Abstract

The central topic of this dissertation is the study of some families of regular planar graphs and maps. We are in particular interested in their asymptotic enumeration in order to understand of the associated uniform random model. In a first part, we give both an exact and an asymptotic enumeration of labelled cubic planar graphs, multigraphs and simple maps, via a recursive scheme following the iterative decompositon of a graph in smaller components of higher connecttivity. In the second part, we apply those results to the study a the uniform random labelled cubic planar graph. We compute for instance the probability of connectivity, and prove that some significant parameters are distributed following a Gaussian limit law: the numbers of cut-vertices, isthmuses, blocks, cherries, near-bricks, and triangles. In the third and last part, we develop the first recursive combinatorial scheme to enumerate 4-regular labelled planar graphs. This scheme is based on a decomposition in terms of connectivity, similar to that of cubic planar graphs, which leads to the exact enumeration of 4-regular planar graphs and simple maps.

Das zentrale Thema dieser Dissertation sind Familien von regulären planaren Graphen und Karten. Insbesondere sind wir an daran interessiert, diese zu zählen und die Zusammenhänge zu deren zufälligen Gegenstücken zu erforschen.

Im ersten Teil geben wir sowohl eine rekursive als auch eine asymptotische Abzählung von kubischen, planaren Graphen, Multigraphen und einfachen Karten, durch eine Dekomposition entlang deren Komponenten. Im zweiten Teil wenden wir diese Resultate auf zufällige kubische planare Graphen an. Insbesondere berechnen wir die Wahrscheinlichkeit von Zusammenhängigkeit, und beweisen das einige bedeutende Parameter normalverteilt sind: die Anzahl der cut-vertices, isthmuses, Blöcke, cherries, near-bricks und Dreiecke. Im dritten und letzten Teil entwickeln wir das erste kombinatorisches Schema, basierend auf einem Dekompositionsschema das ähnlich zu dem im Kontext von kubischen planaren Graphen ist, das zur rekursiven Abzählung von 4-regulären planaren Graphen und einfachen Karten führt.