Unit disk graph
geometric graph theory, a unit disk graph is the intersection graphof 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
induced subgraphof 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 graphK4 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 scienceto 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.]
NP-hardto 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 setcan 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 problemcan 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.
Vietoris–Rips complex, a generalization of the unit disk graph that constructs higher-order topological spaces from unit distances in a metric space
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
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
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
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
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
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
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