Maximal Planar Subgraphs of Fixed Girth in Random Graphs

  • Manuel Fernández School of Computer Science, Carnegie Mellon University
  • Nicholas Sieger Department of Mathematical Sciences, Carnegie Mellon University
  • Michael Tait Department of Mathematical Sciences, Carnegie Mellon University
Keywords: Planar subgraph, Random graph, Threshold

Abstract

In 1991, Bollobás and Frieze showed that the threshold for $G_{n,p}$ to contain a spanning maximal planar subgraph is very close to $p = n^{-1/3}$. In this paper, we compute similar threshold ranges for $G_{n,p}$ to contain a maximal bipartite planar subgraph and for $G_{n,p}$ to contain a maximal planar subgraph of fixed girth $g$.

 

Published
2018-06-08
Article Number
P2.45