wiem totestowanie płaskości można wykonać w O (v) (równoważnie O (e), ponieważ wykresy planarne mają krawędzie O (v)).

Zastanawiam się, czy można to zrobić online w O (1) amortyzowanym czasie, gdy każda krawędź jest dodawana (nadal ogólnie czas O (e)).

Innymi słowy, w tabeli bazy danych reprezentującej krawędzie wykresu i podlegającej ograniczeniu, że reprezentowany wykres jest planarny, ile czasu musi zajmować DBMS odpowiedzialny za zarządzanie ograniczeniem, aby zweryfikować każde proponowane wstawienie? (Dla uproszczenia załóżmy, że nie ma żadnych delecji.) Czy musi ponownie uruchomić jeden z algorytmów testowania planarności O (v), aby przetestować każde proponowane wstawienie lub grupę wstawek?