The genus of a random graph

DOI10.1016/0012-365X(95)00215-IzbMath0834.05023OpenAlexW2078504643WikidataQ127109821 ScholiaQ127109821MaRDI QIDQ1896342

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

surfaceembeddingstriangulationsgenusrandom graph

Mathematics Subject Classification ID

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

Related Items (6)

Classes of graphs embeddable in order-dependent surfaces ⋮ Formation of a giant component in the intersection graph of a random chord diagram ⋮ The genus of the Erd\H{o}s-R\'enyi random graph and the fragile genus property ⋮ Planarity and Genus of Sparse Random Bipartite Graphs ⋮ The Genus of a Random Bipartite Graph ⋮ Triangulations and the Hajós conjecture

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic behavior of the chromatic index for hypergraphs
• Near perfect coverings in graphs and hypergraphs
• Triangulating a surface with a prescribed graph
• The graph genus problem is NP-complete

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