Unit disk graphs
type: Item
instance of: scholarly article
title: Unit disk graphs
zbMATH Open document ID: 0739.05079
DOI: 10.1016/0012-365X(90)90358-O
author: Brent N. Clark
author: Charles J. Colbourn
author: D. S. Johnson
published in: Discrete Mathematics
publication date: 1992-06-25T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 8146
zbMATH Keywords: algorithms
zbMATH Keywords: points in the plane
zbMATH Keywords: unit disk graph
zbMATH Keywords: intersection graph
Wikidata QID: Q56210399
reviewed by: Erich Prisner
MaRDI profile type: Publication
cites work: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
cites work: Some simplified NP-complete graph problems
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: Q4198056
cites work: Q3328583
cites work: Hamilton Paths in Grid Graphs
cites work: The NP-completeness column: An ongoing guide
cites work: The NP-completeness column: an ongoing guide
cites work: Q4142699
cites work: Planar Formulae and Their Uses
cites work: Q3686754
cites work: The Location of Emergency Service Facilities
cites work: Universality considerations in VLSI circuits
description: scientific article; zbMATH DE number 8146