The genus of a random graph

DOI10.1016/0012-365X(95)00215-IMaRDI QIDQ1896342zbMATH OpenOpenAlexWikidataFDO

Authors David A. Grable, Dan S. Archdeacon

Publication date 8 April 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(95)00215-i

zbMATH Keywords

surfacerandom graphtriangulationsembeddingsgenus

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On the genus of a random graph
• The genus of a random bipartite graph
• On the average genus of the random graph
• 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
• Random generations of the countable random graph
• Genus distribution for two classes of graphs
• Genus distributions for two classes of graphs
• Genus distribution for a graph

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 3769674 (Why is no real title available?)
• scientific article; zbMATH DE number 3450230 (Why is no real title available?)
• Asymptotic behavior of the chromatic index for hypergraphs
• Near perfect coverings in graphs and hypergraphs
• The graph genus problem is NP-complete
• Triangulating a surface with a prescribed graph

Cited in

(13)

• Triangulations and the Hajós conjecture
• Genus from sandpile torsor algorithm
• Randomly removing \(g\) handles at once
• On the genus of a random graph
• The genus of a type of graph
• Formation of a giant component in the intersection graph of a random chord diagram
• Planarity and genus of sparse random bipartite graphs
• Classes of graphs embeddable in order-dependent surfaces
• Expected number of faces in a random embedding of any graph is at most linear
• The genus of the Erdős-Rényi random graph and the fragile genus property
• On the average genus of the random graph
• The genus of a random bipartite graph
• An Introduction to Random Topological Graph Theory

This page was built for publication: The genus of a random graph

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