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

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 (inverse-ackermann (total-operations, n)) для случая отсутствия удалений, который обсуждался в статье 1992 года Быстрое тестирование инкрементальной плоскостности , но CiteSeer сейчас недоступен, поэтому я прочитаю подробности позже.

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