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.