On the Number of Edges in Random Planar Graphs.

Journal article

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 13/7n + 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 13/7n - c (for a suitable constant c) then at least this number of edges can be added.

Authors: Gerke, S; McDiarmid, C

• Journal: Combinatorics, Probability and Computing
• Volume: 13
• Issue: 2
• Pages: 165-183
• Publication date: 2004-01-01
• DOI: 10.1017/S0963548303005947
• EISSN: 1469-2163
• ISSN: 0963-5483
• Language: English