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$.
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。