Unit disk graphs (Q1174134): Difference between revisions

Any given \(n\) points in the plane form the vertices of some graph by the convention that distinct points are adjacent whenever their distance is at most 2. The resulting graph is called a unit disk graph, since it is the intersection graph of the unit disks around the given \(n\) points. It is shown that certain hard decision problems remain NP-complete when restricted to unit disk graphs, even when the position of the points is given. These problems are CHROMATIC NUMBER, INDEPENDENT SET, and several others. On the other hand, a maximum cardinality clique in unit disk graphs can be found in polynomial time when the position of the points is given.