Maximal Planar Subgraphs of Fixed Girth in Random Graphs

2017/06/19 by Manuel Fernández, Fernández, Manuel, Nicholas Sieger +3
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1706.06202

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.

Related

• Distribution of the Size of a Largest Planar Matching and Largest Planar Subgraph in Random Bipartite Graphs
• 1-planar graphs with minimum degree at least 3 have bounded girth
• Maximum planar subgraphs in dense graphs
• Extremal Subgraphs of Random Graphs: an Extended Version
• Regular grid subgraphs of maximal girth