Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-10T11:31:43.420Z Has data issue: false hasContentIssue false

On the Number of Edges in Random Planar Graphs

Published online by Cambridge University Press:  03 March 2004

STEFANIE GERKE
Affiliation:
TU München, Institut für Informatik, Arcisstraße 21, 80290 München, Germany (e-mail: gerke@in.tum.de)
COLIN McDIARMID
Affiliation:
University of Oxford, Department of Statistics, South Parks Road, Oxford OX1 3TG, UK (e-mail: cmcd@stats.ox.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider random planar graphs on $n$ labelled nodes, and show in particular that if the graph is picked uniformly at random then the expected number of edges is at least $\frac{13}{7}n +o(n)$. To prove this result we give a lower bound on the size of the set of edges that can be added to a planar graph on $n$ nodes and $m$ edges while keeping it planar, and in particular we see that if $m$ is at most $\frac{13}{7}n - c$ (for a suitable constant~$c$) then at least this number of edges can be added.

Information

Type
Paper
Copyright
2004 Cambridge University Press