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: | , |
|---|---|
| Outros Autores: | |
| Formato: | Journal article |
| Idioma: | English |
| Publicado em: |
2010
|