# Unit disk graph

In

geometric graph theory , a**unit disk graph**is theintersection graph of a family ofunit circle s in theEuclidean plane . That is, we form a vertex for each circle, and connect two vertices by an edge whenever the corresponding circles cross each other.There are several possible definitions of the unit disk graph, equivalent to each other up to a choice of scale factor:

* An intersection graph of equal-radius circles, or of equal-radius disks

* A graph formed from a collection of equal-radius circles, in which two circles are connected by an edge if one circle contains the center of the other circle

* 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 thresholdEvery

induced subgraph of a unit disk graph is also a unit disk graph. 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. Everyunit distance graph , in which we connect two points in a planar point set if their distance is exactly one, is a unit disk graph, but the converse is not true; for instance, thecomplete graph K_{4}is a unit disk graph but not a unit distance graph.Beginning with the work of harvtxt|Huson|Sen|1995, unit disk graphs have been used in

computer science to model the topology of ad-hoc wireless communication networks. In this application, nodes are connected through a direct wireless connection without abase station . It is assumed that all nodes are homogeneous and equipped withomnidirectional antenna s. Node locations are modeled as Euclidean points, and the area within which a signal from one node can be received by another node is modeled as a circle. If all nodes have transmitters of equal power, these circles are all equal. Random geometric graphs, formed as unit disk graphs with randomly generated disk centers, have also been used as a model of percolation and various other phenomena. [*See, e.g., harvtxt|Dall|Christensen|2002.*]It is

NP-hard to determine whether a graph, given without geometry, can be represented as a unit disk graph. [*harvtxt|Breu|Kirkpatrick|1998.*] However, many important and difficult graph optimization problems such asmaximum independent set ,graph coloring , and minimumdominating set can be approximated efficiently by using the geometric structure of these graphs, [*harvtxt|Marathe|Breu|Hunt, III|Ravi|1994; harvtxt|Matsui|2000.*] and themaximum clique problem can be solved exactly for these graphs in polynomial time, given a disk representation. [*harvtxt|Clark|Colbourn|Johnson|1990.*]When a given vertex set forms a subset of a triangular lattice, a necessary and sufficient condition for the perfectness of a unit graph is known. [

*harvtxt|Miyamoto|Matsui|2005.*] For the perfect graphs, a number of NP-complete optimization problems (graph coloring problem ,maximum clique problem , andmaximum independent set problem ) are polynomially solvable.**ee also***

Vietoris–Rips complex , a generalization of the unit disk graph that constructs higher-order topological spaces from unit distances in a metric space**Notes****References*** citation

last1 = Breu

first1 = Heinz

authorlink2 = David G. Kirkpatrick

last2 = Kirkpatrick

first2 = David G.

title = Unit disk graph recognition is NP-hard

journal = Computational Geometry Theory and Applications

volume = 9

issue = 1–2

pages = 3–24

year = 1998* citation

last1 = Clark

first1 = Brent N.

last2 = Colbourn

first2 = Charles J.

authorlink3 = David S. Johnson

last3 = Johnson

first3 = David S.

title = Unit disk graphs

journal = Discrete Mathematics

volume = 86

issue = 1–3

year = 1990

pages = 165–177

doi = 10.1016/0012-365X(90)90358-O* citation

last1 = Dall

first1 = Jesper

last2 = Christensen

first2 = Michael

title = Random geometric graphs

journal = Phys. Rev. E

volume = 66

pages = 016121

year = 2002

id = arxiv|archive = cond-mat|id = 0203026* citation

last1 = Huson

first1 = Mark L.

last2 = Sen

first2 = Arunabha

contribution = Broadcast scheduling algorithms for radio networks

title = Military Communications Conference, IEEE MILCOM '95

year = 1995

pages = 647–651

volume = 2

doi = 10.1109/MILCOM.1995.483546* citation

last1 = Marathe

first1 = Madhav V.

last2 = Breu

first2 = Heinz

last3 = Hunt, III

first3 = Harry B.

last4 = Ravi

first4 = S. S.

last5 = Rosenkrantz

first5 = Daniel J.

title = Geometry based heuristics for unit disk graphs

year = 1994

id = arxiv|archive = math.CO|id = 9409226* citation

last = Matsui

first = Tomomi

title = Approximation Algorithms for Maximum Independent Set Problems and Fractional Coloring Problems on Unit Disk Graphs

journal = Lecture Notes in Computer Science

volume = 1763

pages = 194-200

year = 2000* citation

last1 = Miyamoto

first1 = Yuichiro

last2 = Matsui

first2 = Tomomi

title = Perfectness and Imperfectness of the kth Power of Lattice Graphs

journal = Lecture Notes in Computer Science

volume = 3521

pages = 233-242

year = 2005

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Unit distance graph**— In mathematics, and particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one.… … Wikipedia**Unit disk**— For other uses, see Disc (disambiguation). An open Euclidean unit disk In mathematics, the open unit disk (or disc) around P (where P is a given point in the plane), is the set of points whose distance from P is less than 1 … Wikipedia**Graph coloring**— A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… … Wikipedia**Geometric graph theory**— In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs. Notable geometric… … Wikipedia**Intersection graph**— In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may… … Wikipedia**Code-O-Graph**— The Code O Graph is a field cipher device and identifier from the Captain Midnight radio serial. In the story line they were used by agents of the Secret Squadron, a paramilitary organization headed by Captain Midnight. In addition to their use… … Wikipedia**List of NP-complete problems**— Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… … Wikipedia**Vietoris–Rips complex**— In topology, the Vietoris–Rips complex, also called the Vietoris complex or Rips complex, is an abstract simplicial complex that can be defined from any metric space M and distance delta; by forming a simplex for every finite set of points that… … Wikipedia**Clique problem**— The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… … Wikipedia**List of mathematics articles (U)**— NOTOC U U duality U quadratic distribution U statistic UCT Mathematics Competition Ugly duckling theorem Ulam numbers Ulam spiral Ultraconnected space Ultrafilter Ultrafinitism Ultrahyperbolic wave equation Ultralimit Ultrametric space… … Wikipedia