Maximal planar subgraphs of fixed girth in random graphs
Summary: \textit{B. Bollobás} and \textit{A. M. Frieze} [Random Struct. Algorithms 2, No. 1, 225--231 (1991; Zbl 0766.05077)] 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\).
scientific article