Czy istnieje algorytm wielomianowy do rozwiązywania izomorfizmu grafów dla grafów Delaunaya (skończonych) heksagonalnych teselacji?

Biorąc pod uwagę skończoną płaszczyznę, mam sześciokątną teselację tej płaszczyzny z regularnym sześciokątem o stałej wielkości. Następnie obliczam wykres G Delaunaya dla teselacji. Biorąc pod uwagę taki wykres G, usuwam określone zestawy węzłów na tym wykresie, aby uzyskać wiele podgraphów G. Muszę ustalić, czy podgrupy te są izomorficzne (względem siebie).

Czy istnieje algorytm czasu wielomianowego?

Wiem, że nie ma znanego algorytmu wieloczasowego rozwiązywania izomorfizmu grafów w ogólnym przypadku. Nie jestem jednak pewien, czy nadal tak jest w przypadku tak specyficznych wykresów Delaunaya.

Sądzę, że wszystkie te podgrupy będą wykresami planistycznymi. I myślę, że istnieje skuteczny algorytm dla izomorfizmu grafów planarnych.

ref: Algorytm czasu liniowego dla izomorfizmu grafów płaskich autorstwa JE Hopcroft
JK Wong

UWAGA: Nie jestem ekspertem i być może nie mam sensu.