Counting disk graphs.
A disk graph is the intersection graph of disks in the plane, and a unit disk graph is the intersection graph of same radius disks in the plane. We give upper and lower bounds on the number of labelled unit disk and disk graphs on n vertices. We show that the number of disk graphs on n vertices is n...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2011
|
| _version_ | 1797089291270094848 |
|---|---|
| author | McDiarmid, C Müller, T |
| author_facet | McDiarmid, C Müller, T |
| author_sort | McDiarmid, C |
| collection | OXFORD |
| description | A disk graph is the intersection graph of disks in the plane, and a unit disk graph is the intersection graph of same radius disks in the plane. We give upper and lower bounds on the number of labelled unit disk and disk graphs on n vertices. We show that the number of disk graphs on n vertices is n(3+o(1))n and the number of unit disk graphs on n vertices is n(2+o(1))n. © 2011 Elsevier B.V. |
| first_indexed | 2024-03-07T03:02:06Z |
| format | Journal article |
| id | oxford-uuid:b14f0308-5460-43c9-b8fe-fbbb511467ce |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T03:02:06Z |
| publishDate | 2011 |
| record_format | dspace |
| spelling | oxford-uuid:b14f0308-5460-43c9-b8fe-fbbb511467ce2022-03-27T04:02:59ZCounting disk graphs.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:b14f0308-5460-43c9-b8fe-fbbb511467ceEnglishSymplectic Elements at Oxford2011McDiarmid, CMüller, TA disk graph is the intersection graph of disks in the plane, and a unit disk graph is the intersection graph of same radius disks in the plane. We give upper and lower bounds on the number of labelled unit disk and disk graphs on n vertices. We show that the number of disk graphs on n vertices is n(3+o(1))n and the number of unit disk graphs on n vertices is n(2+o(1))n. © 2011 Elsevier B.V. |
| spellingShingle | McDiarmid, C Müller, T Counting disk graphs. |
| title | Counting disk graphs. |
| title_full | Counting disk graphs. |
| title_fullStr | Counting disk graphs. |
| title_full_unstemmed | Counting disk graphs. |
| title_short | Counting disk graphs. |
| title_sort | counting disk graphs |
| work_keys_str_mv | AT mcdiarmidc countingdiskgraphs AT mullert countingdiskgraphs |