On the Number of Edges in Random Planar Graphs.
- 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.
- Publisher copy:
- Combinatorics, Probability and Computing
- Publication date:
- Pubs id:
- Local pid:
- Source identifiers:
- Deposit date:
- Copyright date:
Views and Downloads
If you are the owner of this record, you can report an update to it here: Report update to this record