Существует ли алгоритм полиномиального времени для решения изоморфизма графов для графов Делоне (конечных) гексагональных тесселяций?

Учитывая конечную плоскость, у меня есть шестиугольная мозаика этой плоскости с регулярным шестиугольником фиксированного размера. Затем я вычисляю граф Делоне G для тесселяции. Учитывая такой граф G, я удаляю определенные множества узлов в этом графе, чтобы получить несколько подграфов G. Мне нужно определить, изоморфны ли эти подграфы (друг другу).

Существует ли для этого алгоритм с полиномиальным временем?

Я знаю, что не существует многовариантного алгоритма для решения изоморфизма графов в общем случае. Но я не уверен, так ли это для таких конкретных графов Делоне.

Я думаю, что все эти подграфы будут более строгими графами. И я думаю, что существует эффективный алгоритм изоморфизма плоских графов.

ref: Алгоритм линейного времени для изоморфизма плоских графов Дж. Э. Хопкрофта,
Дж. К. Вонг

ПРИМЕЧАНИЕ: я не эксперт и, возможно, не имеет никакого смысла.