Gibt es einen Polynom-Zeit-Algorithmus zur Lösung des Graphisomorphismus für Delaunay-Graphen von (endlichen) hexagonalen Tessellationen?

Bei einer endlichen Ebene habe ich eine hexagonale Tessellation dieser Ebene mit einem regulären Sechseck fester Größe. Ich berechne dann den Delaunay-Graphen G für die Tessellation. Bei einem solchen Graphen G lösche ich bestimmte Sätze von Knoten in diesem Graphen, um mehrere Teilgraphen von G zu erhalten. Ich muss bestimmen, ob diese Teilgraphen isomorph (zueinander) sind.

Gibt es dafür einen Polynom-Zeit-Algorithmus?

Ich weiß, dass es im allgemeinen Fall keinen bekannten Polyzeitalgorithmus zum Lösen des Graphisomorphismus gibt. Ich bin mir jedoch nicht sicher, ob dies bei solchen spezifischen Delaunay-Graphen immer noch der Fall ist.

Ich denke, all diese Untergraphen werden Hobelgraphen sein. Und ich denke, dass es einen effizienten Algorithmus für den Isomorphismus von Hobelgraphen gibt.

ref: Linearer Zeitalgorithmus für den Isomorphismus planarer Graphen von JE Hopcroft
JK Wong

HINWEIS: Ich bin kein Experte und mache möglicherweise keinen Sinn.