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...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2004
|
| _version_ | 1826282285656178688 |
|---|---|
| author | Gerke, S McDiarmid, C |
| author_facet | Gerke, S McDiarmid, C |
| author_sort | Gerke, S |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T00:41:32Z |
| format | Journal article |
| id | oxford-uuid:8334dc9e-efa7-44fa-ba43-b28d7da5a42a |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:41:32Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | oxford-uuid:8334dc9e-efa7-44fa-ba43-b28d7da5a42a2022-03-26T21:42:45ZOn the Number of Edges in Random Planar Graphs.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:8334dc9e-efa7-44fa-ba43-b28d7da5a42aEnglishSymplectic Elements at Oxford2004Gerke, SMcDiarmid, CWe 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. |
| spellingShingle | Gerke, S McDiarmid, C On the Number of Edges in Random Planar Graphs. |
| title | On the Number of Edges in Random Planar Graphs. |
| title_full | On the Number of Edges in Random Planar Graphs. |
| title_fullStr | On the Number of Edges in Random Planar Graphs. |
| title_full_unstemmed | On the Number of Edges in Random Planar Graphs. |
| title_short | On the Number of Edges in Random Planar Graphs. |
| title_sort | on the number of edges in random planar graphs |
| work_keys_str_mv | AT gerkes onthenumberofedgesinrandomplanargraphs AT mcdiarmidc onthenumberofedgesinrandomplanargraphs |