Existe um algoritmo de tempo polinomial para resolver o isomorfismo de grafos para gráficos de Delaunay de mosaicos hexagonais (finitos)?

Dado um plano finito, tenho um mosaico hexagonal desse plano com um hexágono regular de tamanho fixo. Em seguida, calculo o gráfico G de Delaunay para o mosaico. Dado esse gráfico G, excluo conjuntos específicos de nós nesse gráfico para gerar vários subgráficos de G. Preciso determinar se esses subgráficos são isomórficos (entre si).

Existe um algoritmo de tempo polinomial para fazer isso?

Eu sei que não existe um algoritmo poli-tempo conhecido para resolver o isomorfismo de grafos no caso geral. Mas não tenho certeza se ainda é o caso de tais gráficos específicos de Delaunay.

Eu acho que todos esses subgráficos serão gráficos mais planos. E eu acho que existe um algoritmo eficiente para o isomorfismo de gráficos mais planos.

ref: Algoritmo de tempo linear para isomorfismo de gráficos planares por JE Hopcroft
JK Wong

NOTA: Não sou especialista e pode não estar fazendo sentido.