Dynamic Planar Graph Isomorphism is in DynFO
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910162402410496 |
|---|---|
| author | Datta, Samir Khan, Asif Tschirbs, Felix Vortmeier, Nils Zeume, Thomas |
| author_facet | Datta, Samir Khan, Asif Tschirbs, Felix Vortmeier, Nils Zeume, Thomas |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_22365 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Dynamic Planar Graph Isomorphism is in DynFO Datta, Samir Khan, Asif Tschirbs, Felix Vortmeier, Nils Zeume, Thomas Logic in Computer Science Computational Complexity 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. |
| title | Dynamic Planar Graph Isomorphism is in DynFO |
| topic | Logic in Computer Science Computational Complexity |
| url | https://arxiv.org/abs/2604.22365 |