The ratio of the number of pairs considered by this algorithm to the number of edges in the eventual graph is a constant, giving the linear time bound. 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. 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. If all nodes have transmitters of equal power, these circles are all equal.
Node locations are modelled as Euclidean points, and the area within which a signal from one node can be received by another node is modelled as a circle. It is assumed that all nodes are homogeneous and equipped with omnidirectional antennas. In this application, nodes are connected through a direct wireless connection without a base station. Therefore, unit disk graphs cannot contain an induced K 1,7 subgraph.īeginning with the work of (Huson Sen), unit disk graphs have been used in computer science to model the topology of ad hoc wireless communication networks. An example of a graph that is not a unit disk graph is the star K 1,7 with one central node connected to seven leaves: if each of seven unit disks touches a common unit disk, some two of the seven disks must touch each other (as the kissing number in the plane is 6). A graph formed from a collection of equal-radius circles, in which two circles are connected by an edge if one circle contains the centre of the other circle.Įvery induced subgraph of a unit disk graph is also a unit disk graph.An intersection graph of equal-radius circles, or of equal-radius disks (see Fig.A graph formed from a collection of points in the Euclidean plane, in which two points are connected if their distance is below a fixed threshold.There are several possible definitions of the unit disk graph, equivalent to each other up to a choice of scale factor:
0 kommentar(er)
