Новый алгоритм проверки пересечений в графах прятался на виду

В октябре 2019 Якоб Хольм и Ева Ротенберг пролистывали работу, опубликованную ими за несколько месяцев до этого – и вдруг поняли, что наткнулись на нечто серьёзное.

Десятилетиями специалисты по информатике пытались разработать быстрый алгоритм для определения того, можно ли добавить к определённому графу рёбра так, чтобы он остался «планарным» – то есть, чтобы его рёбра не пересекались. Однако ни у кого не получалось улучшить алгоритм, опубликованный более 20 лет назад.

Хольм и Ротенберг с удивлением обнаружили, что в их работе есть идея, позволявшая достаточно сильно улучшить этот алгоритм. Она «разобралась с одним из главных препятствий на пути к реальному алгоритму», — сказал Хольм, специалист по информатике из Копенгагенского университета. «Возможно, мы полностью раскрыли этот вопрос».

Парочка поспешила приступить к работе над новой статьёй. Они представили её в июне на симпозиуме по вычислительной теории, проводимом Ассоциацией вычислительной техники, где подробно описали метод проверки графа на планарность, превосходящий предыдущий вариант экспоненциально.