¿Existe un algoritmo de tiempo polinómico para resolver el isomorfismo gráfico para los gráficos de Delaunay de teselaciones hexagonales (finitas)?

Dado un plano finito, tengo una teselación hexagonal de ese plano con un hexágono regular de tamaño fijo. Luego calculo el gráfico de Delaunay G para la teselación. Dado tal gráfico G, elimino conjuntos específicos de nodos en ese gráfico para producir múltiples subgrafías de G. Necesito determinar si estas subgrafías son isomorfas (entre sí).

¿Existe un algoritmo de tiempo polinómico para hacerlo?

Sé que no existe un algoritmo de poli-tiempo conocido para resolver el isomorfismo gráfico en el caso general. Pero no estoy seguro de si sigue siendo el caso para gráficos específicos de Delaunay.

Supongo que todas esas subgrafías serán gráficas más planas. Y creo que hay un algoritmo eficiente para el isomorfismo de los gráficos más planos.

ref: Algoritmo de tiempo lineal para isomorfismo de gráficos planos por JE Hopcroft
JK Wong

NOTA: No soy un experto y podría no tener ningún sentido.