The Evolution of Random Graphs on Surfaces

DOI10.1137/17M113383XMaRDI QIDQ4610182zbMATH OpenOpenAlexFDO

Authors 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

surfacesmaximum degreerandom graphscomponentssubgraphslargest face

Mathematics Subject Classification ID

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

Recommendations

• The evolution of random graphs on surfaces
• Random graphs on surfaces
• scientific article; zbMATH DE number 3168330
• The Evolution of Random Graphs
• scientific article; zbMATH DE number 3173143
• The evolution of uniform random planar graphs
• scientific article; zbMATH DE number 1421319
• scientific article; zbMATH DE number 3902655
• Evolution of the giant component in graphs on orientable surfaces
• scientific article; zbMATH DE number 3966129

Cites work

• scientific article; zbMATH DE number 5130821 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A central limit theorem for the number of degree-\(k\) vertices in random maps
• Asymptotic enumeration and limit laws for graphs of fixed genus
• Asymptotic enumeration and limit laws of planar graphs
• Connectivity for Bridge-addable monotone graph classes
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• Connectivity of addable graph classes
• Degree distribution in random planar graphs
• Evolution of the giant component in graphs on orientable surfaces
• Fast generation of planar graphs
• Generating labeled planar graphs uniformly at random
• On the Maximum Degree of a Random Planar Graph
• On the Number of Edges in Random Planar Graphs
• On the connectivity of random graphs from addable classes
• On the diameter of random planar graphs
• Phase transitions in graphs on orientable surfaces
• Random graphs on surfaces
• Random graphs.
• Random planar graphs
• Random planar graphs with \(n\) nodes and a fixed number of edges
• The Size of the Largest Components in Random Planar Maps
• The distribution of the maximum vertex degree in random planar maps
• The evolution of uniform random planar graphs
• The maximum degree of random planar graphs
• The number of labeled 2-connected planar graphs
• Two critical periods in the evolution of random planar graphs
• Uniform random sampling of planar graphs in linear time

Cited in

(17)

• Random graphs on surfaces
• The evolution of random graphs on surfaces
• Planarity and genus of sparse random bipartite graphs
• The Evolution of Random Graphs
• Universality for random surfaces in unconstrained genus
• Longest and shortest cycles in random planar graphs
• Random graphs embeddable in order-dependent surfaces
• The genus of the Erdős-Rényi random graph and the fragile genus property
• The genus of the Erdős-Rényi random graph and the fragile genus property
• The genus of a random bipartite graph
• Phase transitions in graphs on orientable surfaces
• The evolution of uniform random planar graphs
• The evolution of random graphs on surfaces of non-constant genus
• Expected number of faces in a random embedding of any graph is at most linear
• Concentration of maximum degree in random planar graphs
• Evolution of the giant component in graphs on orientable surfaces
• Classes of graphs embeddable in order-dependent surfaces

Describes a project that uses

Uses Software

• plantri

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4610182)