ich weiß dasPlanaritätstests kann in O (v) (äquivalent O (e)) durchgeführt werden, da planare Graphen O (v) -Kanten haben).

Ich frage mich, ob es online in O (1) amortisierter Zeit gemacht werden kann, wenn jede Kante addiert wird (immer noch O (e) Zeit insgesamt).

Mit anderen Worten, in einer Datenbanktabelle, die Kanten eines Diagramms darstellt und einer Einschränkung unterliegt, dass das dargestellte Diagramm planar ist, wie viel Zeit muss das für die Verwaltung der Einschränkung verantwortliche DBMS für die Validierung jeder vorgeschlagenen Einfügung aufwenden? (Zur Vereinfachung wird angenommen, dass keine Löschungen vorhanden sind.) Muss einer der O (v) -Planaritätstestalgorithmen erneut ausgeführt werden, um jede vorgeschlagene Einfügung oder Gruppe von Einfügungen zu testen?