The Evolution of Random Graphs on Surfaces

DOI10.1137/17M113383XzbMath1383.05292OpenAlexW2963080696MaRDI QIDQ4610182

Chris Dowden, Mihyun Kang, Philipp Sprüssel

Publication date: 6 April 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/17m113383x

zbMATH Keywords

random graphssurfacescomponentsmaximum degreesubgraphslargest face

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07)

Related Items (5)

Classes of graphs embeddable in order-dependent surfaces ⋮ The genus of the Erd\H{o}s-R\'enyi random graph and the fragile genus property ⋮ Concentration of maximum degree in random planar graphs ⋮ Longest and shortest cycles in random planar graphs ⋮ The evolution of random graphs on surfaces

Uses Software

• plantri

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A central limit theorem for the number of degree-\(k\) vertices in random maps
• Degree distribution in random planar graphs
• Random graphs on surfaces
• Evolution of the giant component in graphs on orientable surfaces
• Random planar graphs
• The number of labeled 2-connected planar graphs
• On the connectivity of random graphs from addable classes
• The distribution of the maximum vertex degree in random planar maps
• Generating labeled planar graphs uniformly at random
• The evolution of uniform random planar graphs
• Asymptotic enumeration and limit laws for graphs of fixed genus
• Connectivity of addable graph classes
• Two critical periods in the evolution of random planar graphs
• The maximum degree of random planar graphs
• Uniform random sampling of planar graphs in linear time
• Asymptotic enumeration and limit laws of planar graphs
• Connectivity for Bridge-Addable Monotone Graph Classes
• On the Maximum Degree of a Random Planar Graph
• The Size of the Largest Components in Random Planar Maps
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• On the Number of Edges in Random Planar Graphs
• Phase transitions in graphs on orientable surfaces
• On the Diameter of Random Planar Graphs

This page was built for publication: The Evolution of Random Graphs on Surfaces