Unit disk graph

Unit disk graph

In geometric graph theory, a unit disk graph is the intersection graph of a family of unit circles in the Euclidean 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 threshold

Every 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 K1,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. Every unit 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, the complete graph K4 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 a base station. It is assumed that all nodes are homogeneous and equipped with omnidirectional antennas. 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 as maximum independent set, graph coloring, and minimum dominating set can be approximated efficiently by using the geometric structure of these graphs, [harvtxt|Marathe|Breu|Hunt, III|Ravi|1994; harvtxt|Matsui|2000.] and the maximum 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, and maximum 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

  • 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

  • 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

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”