Journal article icon

Journal article

The Number of Bits Needed to Represent a Unit Disk Graph.

Abstract:
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.
Publication status:
Published

Actions


Access Document


Authors


McDiarmid, C More by this author
Müller, T More by this author

Contributors

Role:
Editor
Journal:
WG
Volume:
6410
Pages:
315-323
Publication date:
2010
DOI:
EISSN:
1611-3349
ISSN:
0302-9743
URN:
uuid:808a1705-3496-42d9-9530-107c20a97f4f
Source identifiers:
107223
Local pid:
pubs:107223
Language:
English

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP