Esistono algoritmi online per i test di planarità?

Question

So che test di planarità può essere eseguito in O (v) (equivalentemente O (e ), poiché i grafici planari hanno il tempo O (v) edge).

Mi chiedo se sia possibile farlo online nel tempo ammortizzato O (1) man mano che viene aggiunto ciascun bordo (ancora tempo O (e) complessivo).

In altre parole, in una tabella di database che rappresenta i bordi di un grafico e soggetta al vincolo che il grafico rappresentato è planare, quanto tempo deve impiegare il DBMS responsabile della gestione del vincolo per convalidare ogni inserimento proposto? (Per semplificazione, supponiamo che non vi siano eliminazioni.) Deve rieseguire uno degli algoritmi di test di planarità O (v) per testare ogni inserimento o gruppo di inserzioni proposti?

Answer 1

Dopo qualche altra ricerca sembra che la risposta sia "sì", ci sono algoritmi online, ma "no" non ce ne sono con il tempo di esecuzione ammortizzato O (1).

Ecco un documento del 1999 sul Journal of ACM, Planarità completamente dinamica test con applicazioni , in cui gli autori hanno scritto:

  

In particolare, consideriamo le seguenti tre operazioni su un grafico planare G: (i) inserire un bordo se il grafico risultante rimane planare; (ii) eliminare un bordo; e (iii) verificare se è possibile aggiungere un bordo al grafico senza violare la planarità. Mostriamo come supportare ciascuna delle suddette operazioni in O (n ^ 2/3) tempo, dove n è il numero di vertici nel grafico. Il limite per test ed eliminazioni è il caso peggiore, mentre il limite per inserimenti è ammortizzato.

Ho anche trovato l'abstract di un articolo del 1989, Incrementale test di planarità rivendicando un O (log n) associato per l'inserimento del bordo, ma non sono sicuro che la loro tecnica copra anche la cancellazione.

L'articolo del 1999 si riferisce anche a un algoritmo O (inverse-ackermann (total-operations, n)) per il caso di nessuna cancellazione, discusso in un articolo del 1992, Test rapido di planarità incrementale , ma al momento CiteSeer non funziona i dettagli più tardi.

La cancellazione essendo utile alla mia applicazione e avendo accesso al documento J. ACM, leggerò ulteriormente sulla strategia O (n ^ 2/3) ammortizzata.