Grafo di dischi

Una collezione di cerchi unitari e il corrispondente grafo di dischi.

Nella teoria geometrica dei grafi, un grafo di dischi è il grafo d'intersezione di una famiglia di dischi unitari nel piano euclideo. Ossia, formiamo un vertice per ciascun disco e connettiamo due vertici mediante uno spigolo ogni volta che i dischi corrispondenti hanno un'intersezione non vuota.

Bibliografia

• Unit disk graph recognition is NP-hard, in Computational Geometry Theory and Applications, vol. 9, 1–2, 1998, pp. 3–24..
• Unit disk graphs, in Discrete Mathematics, vol. 86, 1–3, 1990, pp. 165–177, DOI:10.1016/0012-365X(90)90358-O..
• Random geometric graphs, in Phys. Rev. E, vol. 66, 2002, p. 016121, DOI:10.1103/PhysRevE.66.016121..
• Military Communications Conference, IEEE MILCOM '95, vol. 2, 1995, pp. 647–651, DOI:10.1109/MILCOM.1995.483546..
• Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SCG'11), June 13–15, 2011, Paris, France, 2011, pp. 308–314..
• Geometry based heuristics for unit disk graphs, 1994..
• Tomomi Matsui, Approximation Algorithms for Maximum Independent Set Problems and Fractional Coloring Problems on Unit Disk Graphs, in Lecture Notes in Computer Science, vol. 1763, 2000, pp. 194–200, DOI:10.1007/978-3-540-46515-7_16..
• Integer realizations of disk and segment graphs, 2011.
• Perfectness and Imperfectness of the kth Power of Lattice Graphs, in Lecture Notes in Computer Science, vol. 3521, 2005, pp. 233–242, DOI:10.1007/11496199_26..
• Robust algorithms for restricted domains, in Journal of Algorithms, vol. 48, n. 1, 2003, pp. 160–172, DOI:10.1016/S0196-6774(03)00048-8..

Voci correlate

• Complesso di Vietoris-Rips, una generalizzazione del grafo di dischi che costruisce spazi topologici di ordine superiore da distanze unitarie in uno spazio metrico
• Grafo a distanza unitaria, un grafo formato connettendo punti che sono esattamente a distanza uno piuttosto che (come qui) al massimo a una data soglia