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

Michael Drmota, Omer Gimenez, Marc Noy

Published 2010-08-31Version 1

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.