Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-24T02:23:18.973Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Number of Edges in Random Planar Graphs

Published online by Cambridge University Press:  03 March 2004

STEFANIE GERKE  and
COLIN McDIARMID
STEFANIE GERKE
Affiliation:
TU München, Institut für Informatik, Arcisstraße 21, 80290 München, Germany (e-mail: [email protected])
COLIN McDIARMID
Affiliation:
University of Oxford, Department of Statistics, South Parks Road, Oxford OX1 3TG, UK (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 13 , Issue 2 , March 2004 , pp. 165 - 183
Copyright
2004 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)