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...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Journal article |
| Language: | English |
| Published: |
2010
|