Paper: Dynamic Planar Graph Isomorphism Is in DynFO (at LICS 2026)

Authors: Samir Datta Asif Khan Felix Tschirbs Nils Vortmeier Thomas Zeume

Open access: https://doi.org/10.4230/LIPIcs.LICS.2026.36

Abstract

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.

BibTeX

  @InProceedings{DattaKhanTschirbsVo-DynamicPlanarGraphI,
    author = 	 {Samir Datta and Asif Khan and Felix Tschirbs and Nils Vortmeier and Thomas Zeume},
    title = 	 {Dynamic Planar Graph Isomorphism Is in DynFO},
    booktitle =  {Proceedings of the Forty-First Annual Symposium on Logic in Computer Science (LICS 2026)},
    year =	 {2026},
    month =	 {July}, 
    pages =      {36:1--36:25},
    location =   {Lisbon, Portugal}, 
    publisher =	 {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
    doi =        {10.4230/LIPIcs.LICS.2026.36}
  }