Grafo di dischi
# 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.

## Caratterizzazioni

Ci sono varie definizioni possibili del grafo di dischi, l'una equivalente all'altra fino alla scelta di un fattore di scala:

* Un grafo d'intersezione di cerchi di uguale raggio, o di dischi di uguale raggio
* Un grafo formato da una collezione di dischi di uguale raggio, in cui due cerchi sono connessi da uno spigolo se un cerchio contiene il centro dell'altro cerchio
* Un grafo formato da una collezione di punti nel piano euclideo, nel quale due punti sono connessi se la loro distanza è al di sotto di una soglia fissa

## Proprietà

Ogni sottografo indotto di un grafo di dischi è anch'esso un grafo di dischi. Un esempio di un grafo che non è un grafo di dischi è la stella $K_{1,7}$ con un nodo centrale connesso a sette foglie: se ciascuno dei sette dischi tocca un disco comune, qualche coppia dei sette dischi deve toccarsi tra loro (in quanto il numero di osculazione nel piano è 6). Perciò, i grafi di dischi non possono contenere un sottografo indotto $K_{1,7}.$

## Applicazioni

A cominciare dal lavoro di Huson & Sen (1995), i grafi di dischi sono stati usati in informatica per modellare la topologia delle reti di comunicazione senza fili ad hoc. In questa applicazione, i nodi sono connessi attraverso una connessione senza fili diretta senza una stazione base. Si assume che tutti i nodi siano omogenei e attrezzati con antenne omnidirezionali. Le localizzazioni dei nodi modellati come punti euclidei, e l'area all'interno della quale un segnale proveniente da un nodo può essere ricevuto da un altro nodo è modellata come un cerchio. Se tutti i nodi hanno trasmittenti di uguale potenza, questi cerchi sono tutti uguali. Grafi geometrici casuali, formati come grafi di dischi con i centri dei dischi generati in modo casuale, sono stati usati anche come modello della percolazione e di vari altri fenomeni.

## Complessità computazionale

È NP-difficile (più specificamente, completo per la teoria esistenziale dei numeri reali) determinare se un grafo, dato senza geometria, possa essere rappresentato come un grafo di dischi. In aggiunta, è dimostrabilmente impossibile emettere in tempo polinomiale le coordinate esplicite della rappresentazione di un grafo di dischi: esistono grafi di dischi che richiedono esponenzialmente molti bit di precisione in una qualsiasi rappresentazione di questo tipo.

Tuttavia, molti importanti e difficili problemi di ottimizzazione dei grafi quali l'insieme indipendente massimo, la colorazione dei grafi e l'insieme dominante minimo possono essere approssimati in modo efficiente usando la struttura geometrica di questi grafi, e il problema della cricca massima può essere risolto esattamente per questi grafi in tempo polinomiale, data una rappresentazione mediante dischi. In modo più forte, se a un grafo si dà un'entrata, è possibile produrre in tempo polinomiale o una cricca massima o una dimostrazione che il grafo non è un grafo di dischi.

Quando un dato insieme di vertici forma un sottoinsieme di un reticolo triangolare, è nota una condizione necessaria e sufficiente per la perfezione di un grafo di dischi. Per i grafi perfetti, numerosi problemi di ottimizzazione NP-completi (problema della colorazione dei grafi, problema della cricca massima e problema del massimo insieme indipendente) sono polinomialmente risolvibili.

