Graphe de disques

In geometric graph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is, it is a graph with one vertex for each disk in the family, and with an edge between two vertices whenever the corresponding vertices lie within a unit distance of each other. They are commonly formed from a Poisson point process, making them a simple example of a random structure. There are several possible definitions of the unit disk graph, equivalent to each other up to a choice of scale factor: Unit disk graphs are the graph formed from a collection of points in the Euclidean plane, with a vertex for each point and an edge connecting each pair of points whose distance is below a fixed threshold. Unit disk graphs are the intersection graphs of equal-radius circles, or of equal-radius disks. These graphs have a vertex for each circle or disk, and an edge connecting each pair of circles or disks that have a nonempty intersection. Unit disk graphs may be formed in a different way from a collection of equal-radius circles, by connecting two circles with an edge whenever one circle contains the center of the other circle. Every induced subgraph of 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 with one central node connected to six leaves: if each of six unit disks touches a common unit disk, some two of the six disks must touch each other. Therefore, unit disk graphs cannot contain an induced subgraph. Infinitely many other forbidden induced subgraphs are known. The number of unit disk graphs on labeled vertices is within an exponential factor of . This rapid growth implies that unit disk graphs do not have bounded twin-width. Beginning with the work of , unit disk graphs have been used in computer science to 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.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (5)

Graphe de disques

En théorie des graphes, un graphe de disques (ou disk graph en anglais) est le graphe d'intersection d'une collection de disques. C'est une extension du concept de graphe d'intervalle à la dimension 2. Formellement, G est un graphe de disques s'il existe une collection de disques dans le plan dont les centres sont en bijection avec les sommets de G et telle que deux disques s'intersectent si et seulement si les sommets correspondants sont reliés par une arête dans G.

Graphe distance-unité

En mathématiques, plus particulièrement en théorie des graphes, un graphe distance-unité est un graphe s'obtenant à partir d'un ensemble de points du plan euclidien en reliant par une arête toutes les paires de points étant à une distance de 1. Les arêtes peuvent se croiser si bien qu'un graphe distance-unité n'est pas nécessairement un graphe planaire. S'il n'y a pas de croisement entre les arêtes, alors le graphe est qualifié de graphe allumette.

Graphe d'intersection

En théorie des graphes, un graphe d'intersection est un graphe représentant les intersections d'une famille d'ensembles. Plus précisément, pour une famille d'ensembles finie donnée, on associe à chaque ensemble un sommet, et deux sommets sont reliés par une arête si les ensembles ont une intersection non nulle. Beaucoup de familles de graphe sont définies par l'intersection d'ensembles géométriques, par exemple des sphères dans le plan, ou des intervalles sur une droite.