The maximum degree of planar graphs I. Series-parallel graphs

2010/08/31 by Michael Drmota, Drmota, Michael, Omer Giménez +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1008.5361

openalex publication_date 2010/08/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that the maximum degree Δ_n of a random series-parallel graph with n vertices satisfies Δ_n/log n → c in probability, and 𝔼 Δ_n ∼ c log n for a computable constant c>0. The same result holds for outerplanar graphs.

Citations

• Singularity Analysis of Generating Functions
• Degree distribution in random planar graphs

Related

• Degree distribution in random planar graphs
• Concentration of maximum degree in random planar graphs
• Maximum degree in minor-closed classes of graphs
• Random planar maps and graphs with minimum degree two and three
• Two point concentration of maximum degree in sparse random planar graphs