Abstract
We study the random planar graph process introduced by Gerke et al. [Random Structures Algorithms, 32 (2008), pp. 236-261]: Begin with an empty graph on n vertices, consider the edges of the complete graph Kn one by one in a random ordering, and at each step add an edge to a current graph only if the graph remains planar. They studied the number of edges added up to step t for "large" t = ω (n). In this paper we extend their results by determining the asymptotic number of edges added up to step t in the early evolution of the process when t = O(n). We also show that this result holds for a much more general class of graphs, including outerplanar graphs, planar graphs, and graphs on surfaces.
Originalsprache | englisch |
---|---|
Seiten (von - bis) | 146-162 |
Seitenumfang | 17 |
Fachzeitschrift | SIAM Journal on Discrete Mathematics |
Jahrgang | 37 |
Ausgabenummer | 1 |
DOIs | |
Publikationsstatus | Veröffentlicht - 31 März 2023 |
ASJC Scopus subject areas
- Allgemeine Mathematik
Fields of Expertise
- Information, Communication & Computing