Gibt es Online-Algorithmen für Planheitsprüfung?

Question

Ich weiß, dass Planarität testen in O getan werden kann, (v) (äquivalent O (e ), da planare Graphen O (v) Kanten) Zeit haben.

Ich frage mich, ob es online im O getan werden kann (1) Zeit amortisiert, da jede Kante (noch O (e) Zeit insgesamt) hinzugefügt wird.

Mit anderen Worten, in einer Datenbanktabelle darstellt Kanten eines Graphen und unterliegt einer Beschränkung, daß die dargestellte Graph eben ist, wie viel Zeit muss das DBMS verantwortlich für die Einschränkung der Verwaltung nehmen jede vorgeschlagene Einfügung zu bestätigen? (Zur Vereinfachung wird angenommen, dass es keine Streichungen.) Muss es erneut ausführen eine der O (v) Planarität Testalgorithmen jede vorgeschlagene Einfügung oder eine Gruppe von Einfügungen zu testen?

Answer 1

Nach etwas mehr Forschung scheint es, dass die Antwort „ja“ lautet, gibt es Online-Algorithmen, aber „nein“ es gibt keine mit O (1) abgeschrieben Zeit ausgeführt wird.

Hier ist ein 1999 Papier im Journal of the ACM, Voll dynamische Planarität Tests mit Anwendungen , in denen die Autoren schrieben:

  

Insbesondere betrachten wir die folgenden drei Operationen auf einem ebenen Graphen G: (i) einen Rand ein, wenn der sich ergebende Graph planar bleibt; (Ii) eine Kante löschen; und (iii) Prüfung, ob eine Kante zu dem Graphen hinzugefügt werden könnte, ohne Planarität zu verletzen. Wir zeigen, wie jede der obigen Operationen in O unterstützen (n ^ 2/3) die Zeit, wobei n die Anzahl der Scheitelpunkte in dem Graphen ist. Die Schranke für Tests und Deletionen ist Worst-Case, während die Grenze für Einfügungen abgeschrieben wird.

Ich fand auch die Zusammenfassung eines 1989 Papier, Incremental Planheitsprüfung einen O behauptet (log n) für die Kanten Einfügung gebunden, aber ich bin nicht sicher, ob ihre Technik Löschen als auch abdeckt.

1999 Das Papier bezieht sich auch auf einen O (Invers-ackermann (Gesamt-Operationen, n)) Algorithmus für den Fall ohne Deletionen, 1992 in einem Papier beschrieben,