Существуют ли онлайн-алгоритмы для проверки планарности?

Question

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

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

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

Answer 1

После еще одного исследования выясняется, что ответ «да», есть онлайн-алгоритмы, но «нет» нет ни одного с O (1) амортизированным временем выполнения.

Вот статья 1999 года в Журнале ACM, Полностью динамическое тестирование плоскостности с приложениями , в котором авторы написали:

В частности, мы рассмотрим следующие три операции на плоском графе G: (i) вставить ребро, если результирующий граф остается плоским; (ii) удалить ребро; и (iii) проверить, может ли ребро быть добавлено к графу без нарушения плоскостности. Мы покажем, как поддерживать каждую из вышеуказанных операций за O (n ^ 2/3) времени, где n - количество вершин в графе. Граница для тестов и удалений является наихудшим случаем, тогда как граница для вставок амортизируется.

Я также нашел реферат статьи 1989 года, Тест на возрастающую плоскостность , требующий O (log n), ограниченного для вставки ребер, но я не уверен, что их метод также охватывает удаление.

В работе 1999 года также упоминается алгоритм O (обратный-аккерманн (total-операций, n)) для случая отсутствия удалений, обсуждаемый в статье 1992 года: Быстрое тестирование инкрементальной плоскостности , но CiteSeer в данный момент не работает, поэтому подробности я прочитаю позже.

Удаление, полезное для моего приложения и имеющее доступ к статье J. ACM, я собираюсь прочитать далее о стратегии амортизации O (n ^ 2/3).