я знаю этотестирование на плоскостность может быть сделано в O (v) (эквивалентно O (e), так как планарные графы имеют O (v) ребер) времени.

Интересно, можно ли это сделать онлайн за O (1) амортизированное время по мере добавления каждого ребра (по-прежнему O (e) время в целом).

Другими словами, в таблице базы данных, представляющей ребра графа и подчиненной ограничению того, что представляемый граф является плоским, сколько времени должно занять СУБД, ответственная за управление ограничением, для проверки каждой предложенной вставки? (Для упрощения предположим, что исключений нет.) Должен ли он повторно запустить один из алгоритмов тестирования планарности O (v), чтобы проверить каждую предложенную вставку или группу вставок?