Unit disk graph

They are commonly formed from a Poisson point process, making them a simple example of a random structure.

[3] This rapid growth implies that unit disk graphs do not have bounded twin-width.

[4] Beginning with the work of Huson & Sen (1995), unit disk graphs have been used in computer science to model the topology of ad hoc wireless communication networks.

It is assumed that all nodes are homogeneous and equipped with omnidirectional antennas.

Random geometric graphs, formed as unit disk graphs with randomly generated disk centres, have also been used as a model of percolation and various other phenomena.

[5] If one is given a collection of unit disks (or their centres) in a space of any fixed dimension, it is possible to construct the corresponding unit disk graph in linear time, by rounding the centres to nearby integer grid points, using a hash table to find all pairs of centres within constant distance of each other, and filtering the resulting list of pairs for the ones whose circles intersect.

[7] Additionally, it is provably impossible in polynomial time to output explicit coordinates of a unit disk graph representation: there exist unit disk graphs that require exponentially many bits of precision in any such representation.