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: | , |
|---|---|
| מחברים אחרים: | |
| פורמט: | Journal article |
| שפה: | English |
| יצא לאור: |
2010
|