Random graphs on surfaces

DOI10.1016/J.JCTB.2007.11.006MaRDI QIDQ933680zbMATH OpenOpenAlexFDO

Authors Colin McDiarmid

Publication date 24 July 2008

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2007.11.006

zbMATH Keywords

graph embeddable on a surfacePlanar graphuniform random graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Random graphs (graph-theoretic aspects) (05C80) Relations of low-dimensional topology with graph theory (57M15)

Review text

Various asymptotic enumerative results for planar graphs are extended to simple graphs embeddable on an arbitrary surface \(S\). In particular, the growth constants for labeled and unlabeled embeddable graphs are shown to be independent of \(S\).

Recommendations

• scientific article; zbMATH DE number 1421319
• The evolution of random graphs on surfaces
• The Evolution of Random Graphs on Surfaces
• Random regular graphs and the systole of a random surface
• scientific article; zbMATH DE number 845673
• Random \(k\)-surfaces
• Random planar graphs and beyond
• Graphs on surfaces
• scientific article; zbMATH DE number 5016711
• Random planar graphs

Cites work

• 0-1 laws for maps
• A pattern for the asymptotic number of rooted maps on surfaces
• Almost all maps are asymmetric
• Almost all rooted maps have large representativity
• Asymptotic normality determined by high moments, and submap counts of random maps
• Blocks and the nonorientable genus of graphs
• Coefficients of functional compositions often grow smoothly
• Generating Outerplanar Graphs Uniformly at Random
• Graphs on surfaces
• scientific article; zbMATH DE number 5130821 (Why is no real title available?)
• scientific article; zbMATH DE number 1146225 (Why is no real title available?)
• scientific article; zbMATH DE number 2038777 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 5050599 (Why is no real title available?)
• On random planar graphs, the number of planar graphs and their triangulations
• On the independence ratio of a graph
• On the Maximum Degree of a Random Planar Graph
• On the Number of Edges in Random Planar Graphs
• On the number of series parallel and outerplanar graphs
• Planar graphs, via well-orderly maps and trees
• Proper minor-closed families are small
• Random cubic planar graphs
• Random planar graphs
• Random planar graphs with n nodes and a fixed number of edges
• Random planar graphs with given average degree
• Separating and nonseparating disjoint homotopic cycles in graph embeddings
• Submap Density and Asymmetry Results for Two Parameter Map Families
• Submaps of maps. I: General 0-1 laws
• The asymptotic number of rooted maps on a surface
• The asymptotic number of rooted maps on a surface. II: Enumeration by vertices and faces
• The asymptotic number of rooted nonseparable maps on a surface
• The number of labeled 2-connected planar graphs

Cited in

(26)

• The evolution of random graphs on surfaces
• Logical limit laws for minor-closed classes of graphs
• Weakly distinguishing graph polynomials on addable properties
• Asymptotic enumeration and limit laws for graphs of fixed genus
• Concentration of maximum degree in random planar graphs
• Local convergence of random planar graphs
• Random maps
• Two critical periods in the evolution of random planar graphs
• Graph classes with given 3-connected components: asymptotic enumeration and random graphs
• Random graphs from a minor-closed class
• Counting planar graphs and related families of graphs
• On some putative graph-theoretic counterexamples to the principle of the identity of indiscernibles
• Random graphs from a weighted minor-closed class
• The Evolution of Random Graphs on Surfaces
• Unlabelled Gibbs partitions
• Phase transitions in graphs on orientable surfaces
• Random graphs containing few disjoint excluded minors
• Degree distribution in random planar graphs
• Classes of graphs embeddable in order-dependent surfaces
• Longest and shortest cycles in random planar graphs
• Random graphs embeddable in order-dependent surfaces
• Unprovability threshold for the planar graph minor theorem
• On graphs with few disjoint \(t\)-star minors
• Pendant appearances and components in random graphs from structured classes
• The evolution of random graphs on surfaces of non-constant genus
• Growth constants of minor-closed classes of graphs

This page was built for publication: Random graphs on surfaces

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