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

Abstract

We prove that the maximum degree ${\Delta }_n$ of a random series-parallel graph with $n$ vertices satisfies ${\Delta }_n/\log n\to c$ in probability, and $\mathbb{E}{\Delta }_n\sim c\log n$ for a computable constant $c>0$. The same result holds for outerplanar graphs.

38 pages