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...
| Asıl Yazarlar: | , |
|---|---|
| Diğer Yazarlar: | |
| Materyal Türü: | Journal article |
| Dil: | English |
| Baskı/Yayın Bilgisi: |
2010
|