zbMATH — the first resource for mathematics

Unit disk graphs. (English) Zbl 0739.05079
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.

05C85 Graph algorithms (graph-theoretic aspects)
05C99 Graph theory
Full Text: DOI
[1] Clark, B.N., Unit disk graphs, () · Zbl 0739.05079
[2] Edmonds, J.; Karp, R.M., Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, 19, 248-264, (1972) · Zbl 0318.90024
[3] Garey, M.R.; Johnson, D.S.; Stockmeyer, L., Some simplified NP-complete graph problems, Theoret. comput. sci., 1, 237-267, (1976) · Zbl 0338.05120
[4] Garey, M.R.; Johnson, D.S., The rectilinear Steiner tree problem is NP-complete, SIAM J. appl. math., 32, 826-834, (1977) · Zbl 0396.05009
[5] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman New York · Zbl 0411.68039
[6] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[7] Hale, W.K., Frequency assignment: theory and applications, Proc IEEE, 68, 1497-1514, (1980)
[8] Itai, A.; Papadimitriou, C.H.; Szwarcfiter, J.L., Hamilton paths in grid graphs, SIAM J. comput., 11, 676-686, (1982) · Zbl 0506.05043
[9] Johnson, D.S., The NP-completeness column: an ongoing guide, J. algorithms, 3, 182-195, (1982) · Zbl 0494.68049
[10] Johnson, D.S., The NP-completeness column: an ongoing guide, J. algorithms, 6, 434-451, (1985) · Zbl 0608.68032
[11] Johnson, D.S., The NP-completeness column: an ongoing guide, J. algorithms, 8, 438-448, (1987) · Zbl 0633.68022
[12] Kammerlander, K., C 900 — an advanced mobile radio telephone system with optimum frequency utilization, IEEE trans. selected areas in communication, 2, 589-597, (1984)
[13] Karp, R.M., Reducibility among combinatorial problems, (), 85-104 · Zbl 0366.68041
[14] J. Kilian, personal communication.
[15] Lichtenstein, D., Planar formulae and their uses, SIAM J. comput., 11, 329-343, (1982) · Zbl 0478.68043
[16] Masuyama, S.; Ibaraki, T.; Hasegawa, T., The computational complexity of the M-center problems in the plane, Trans. IECE Japan, E64, 57-64, (1981)
[17] Mohring, R.H., Algorithmic aspects of comparability graphs and interval graphs, (), 41-101
[18] Toregas, C.; Swain, R.; Revelle, C.; Bergeman, L., The location of emergency service facilities, Oper. res., 19, 1363-1373, (1971) · Zbl 0224.90048
[19] Valiant, L.G., Universality considerations in VLSI circuits, IEEE trans. computers, 30, 135-140, (1981) · Zbl 0455.94046
[20] Yeh, Y.; Wilson, J.; Schwartz, S.C., Outage probability in mobile telephony with directive antennas and macrodiversity, IEEE trans. selected areas in communication, 2, 507-511, (1984)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.