{
  "id": "2110.01952",
  "version": "v2",
  "published": "2021-10-05T11:29:12.000Z",
  "updated": "2022-06-13T08:01:03.000Z",
  "title": "The early evolution of the random graph process in planar graphs and related classes",
  "authors": [
    "Mihyun Kang",
    "Michael Missethan"
  ],
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "We study the random planar graph process introduced by Gerke, Schlatter, Steger, and Taraz [The random planar graph process, Random Structures Algorithms 32 (2008), no. 2, 236--261; MR2387559]: Begin with an empty graph on $n$ vertices, consider the edges of the complete graph $K_n$ 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=\\omega (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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2022-06-13T08:01:03.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C10"
    ],
    "keywords": [
      "random graph process",
      "early evolution",
      "random planar graph process",
      "related classes",
      "random structures algorithms"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}