Michael Drmota
ABSTRACT
Let Pn denote a graph drawn uniformly at random from the class of all simple planar graphs with n vertices. We show that the maximum degree of a vertex in Pn is with probability 1 − o(1) asymptotically equal to c log n, where c ≈ 2.529 is determined explicitly. A similar result is also true for random 2-connected planar graphs.
Our analysis combines two orthogonal methods that complement each other. First, in order to obtain the upper bound, we resort to exact methods, i.e., to generating functions and analytic combinatorics. This allows us to obtain fairly precise asymptotic estimates for the expected number of vertices of any given degree in Pn. On the other hand, for the lower bound we use Boltzmann sampling. In particular, by tracing the execution of an adequate algorithm that generates a random planar graph, we are able to explicitly find vertices of sufficiently high degree in Pn.
Index Terms
- The maximum degree of random planar graphs
Recommendations
Covering planar graphs with forests, one having bounded maximum degree
We prove that every planar graph has an edge partition into three forests, one having maximum degree at most 4. This answers a conjecture of Balogh, Kochol, Pluhar and Yu [J. Balogh, M. Kochol, A. Pluhar, X. Yu, Covering planar graphs with forests, J. ...
Note on 3-choosability of planar graphs with maximum degree 4
AbstractDeciding whether a planar graph (even of maximum degree 4) is 3-colorable is NP-complete. Determining subclasses of planar graphs being 3-colorable has a long history, but since Grötzsch’s result that triangle-free planar graphs are ...
Acyclic improper colourings of graphs with bounded maximum degree
For graphs of bounded maximum degree, we consider acyclic t-improper colourings, that is, colourings in which each bipartite subgraph consisting of the edges between two colour classes is acyclic, and each colour class induces a graph with maximum ...
Comments