Dynamic Planar Graph Isomorphism is in DynFO
It solves the dynamic planar graph isomorphism problem within first-order logic, advancing the understanding of dynamic complexity for a fundamental graph problem.
The paper shows that the dynamic planar graph isomorphism problem, where graphs undergo edge insertions and deletions, can be maintained in the dynamic descriptive complexity class DynFO, implying a dynamic constant-time parallel algorithm with polynomial-size auxiliary data.
Consider two planar graphs which are subject to edge insertions and deletions. We show that whether the two graphs are isomorphic can be maintained with first-order logic formulas and auxiliary data of polynomial size. This places the dynamic planar graph isomorphism problem into the dynamic descriptive complexity class DynFO. As a consequence, there is a dynamic constant-time parallel algorithm with polynomial-size auxiliary data which maintains whether two dynamic planar graphs are isomorphic.