Apakah ada algoritma polinomial-waktu untuk menyelesaikan isomorfisme grafik untuk grafik Delaunay dari tessellations (terbatas) heksagonal?

Diberi bidang terbatas, saya memiliki tessellation heksagonal dari pesawat itu dengan hexagon reguler ukuran tetap. Saya kemudian menghitung grafik Delaunay G untuk tessellation. Diberikan grafik G seperti itu, saya menghapus set node tertentu dalam grafik itu untuk menghasilkan banyak subgraf G. Saya perlu menentukan apakah subgraf ini isomorfik (satu sama lain).

Apakah ada algoritma waktu polinomial untuk melakukannya?

Saya tahu bahwa tidak ada algoritma tahu waktu untuk menyelesaikan isomorfisma grafik pada kasus umum. Tapi saya tidak yakin apakah masih berlaku untuk grafik Delaunay tertentu.

Saya kira semua subgraph itu akan menjadi grafik planer. Dan saya pikir ada algoritma yang efisien untuk isomorfisme grafik planer.

ref: Algoritma waktu linear untuk isomorfisme grafik planar oleh JE Hopcroft
JK Wong

CATATAN: Saya bukan ahli dan mungkin tidak masuk akal.