The Number of Bits Needed to Represent a Unit Disk Graph.
We prove that for sufficiently large n, there exist unit disk graphs on n vertices such that for every representation with disks in the plane at least c√n bits are needed to write down the coordinates of the centers of the disks, for some c> 1. We also show that dn bits always suffice, for so...
| 主要な著者: | , |
|---|---|
| その他の著者: | |
| フォーマット: | Journal article |
| 言語: | English |
| 出版事項: |
2010
|
| _version_ | 1826281734483738624 |
|---|---|
| author | McDiarmid, C Müller, T |
| author2 | Thilikos, D |
| author_facet | Thilikos, D McDiarmid, C Müller, T |
| author_sort | McDiarmid, C |
| collection | OXFORD |
| description | We prove that for sufficiently large n, there exist unit disk graphs on n vertices such that for every representation with disks in the plane at least c√n bits are needed to write down the coordinates of the centers of the disks, for some c> 1. We also show that dn bits always suffice, for some d>1. © 2010 Springer-Verlag. |
| first_indexed | 2024-03-07T00:33:16Z |
| format | Journal article |
| id | oxford-uuid:808a1705-3496-42d9-9530-107c20a97f4f |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:33:16Z |
| publishDate | 2010 |
| record_format | dspace |
| spelling | oxford-uuid:808a1705-3496-42d9-9530-107c20a97f4f2022-03-26T21:24:01ZThe Number of Bits Needed to Represent a Unit Disk Graph.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:808a1705-3496-42d9-9530-107c20a97f4fEnglishSymplectic Elements at Oxford2010McDiarmid, CMüller, TThilikos, DWe prove that for sufficiently large n, there exist unit disk graphs on n vertices such that for every representation with disks in the plane at least c√n bits are needed to write down the coordinates of the centers of the disks, for some c> 1. We also show that dn bits always suffice, for some d>1. © 2010 Springer-Verlag. |
| spellingShingle | McDiarmid, C Müller, T The Number of Bits Needed to Represent a Unit Disk Graph. |
| title | The Number of Bits Needed to Represent a Unit Disk Graph. |
| title_full | The Number of Bits Needed to Represent a Unit Disk Graph. |
| title_fullStr | The Number of Bits Needed to Represent a Unit Disk Graph. |
| title_full_unstemmed | The Number of Bits Needed to Represent a Unit Disk Graph. |
| title_short | The Number of Bits Needed to Represent a Unit Disk Graph. |
| title_sort | number of bits needed to represent a unit disk graph |
| work_keys_str_mv | AT mcdiarmidc thenumberofbitsneededtorepresentaunitdiskgraph AT mullert thenumberofbitsneededtorepresentaunitdiskgraph AT mcdiarmidc numberofbitsneededtorepresentaunitdiskgraph AT mullert numberofbitsneededtorepresentaunitdiskgraph |