arxiv: 2604.22365 · v1 · submitted 2026-04-24 · 💻 cs.LO · cs.CC

Recognition: unknown

Dynamic Planar Graph Isomorphism is in DynFO

Samir Datta , Asif Khan , Felix Tschirbs , Nils Vortmeier , Thomas Zeume

Authors on Pith no claims yet

Pith reviewed 2026-05-08 09:42 UTC · model grok-4.3

classification 💻 cs.LO cs.CC

keywords dynamic planar graph isomorphismDynFOfirst-order logicauxiliary dataedge insertions and deletionsdescriptive complexityparallel algorithms

0 comments

The pith

Two planar graphs undergoing edge insertions and deletions can have their isomorphism status maintained using first-order logic formulas with polynomial auxiliary data.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the problem of checking whether two planar graphs remain isomorphic as edges are added or removed can be solved by maintaining certain first-order logic formulas and a polynomial amount of auxiliary information. This places the dynamic planar graph isomorphism problem in the class DynFO. A sympathetic reader would care because membership in DynFO implies the existence of constant-time parallel algorithms that use only polynomial extra storage to track the isomorphism status. The result extends static results on planar graph isomorphism to the dynamic setting where graphs change over time.

Core claim

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.

What carries the argument

First-order logic formulas together with polynomial-size auxiliary relations that are updated to track isomorphism under edge insertions and deletions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The maintenance technique might extend to isomorphism for other restricted graph families where static versions are already tractable.
Practical systems that process evolving planar networks could use this to avoid full recomputation after each change.
It raises the question of whether the same FO maintenance works for non-planar graphs or requires the planarity restriction.

Load-bearing premise

The specific first-order formulas and auxiliary relations correctly maintain the isomorphism status for all possible sequences of edge insertions and deletions on planar graphs.

What would settle it

A sequence of edge insertions and deletions on two planar graphs where the maintained isomorphism status differs from the true isomorphism after some update.

Figures

Figures reproduced from arXiv: 2604.22365 by Asif Khan, Felix Tschirbs, Nils Vortmeier, Samir Datta, Thomas Zeume.

**Figure 3.** Figure 3: after the edge (u, v) is deleted only the subpath from component I1 to component I2 is relevant for ρ ′ . As in the previous case [2 +−→ 3] we first assume that the subpaths from component D1 to the last triconnected component B1 before I1 and from D2 to the last component B2 before I2 are both not single cycle components but either a 3-connected component or a non-trivial path of more than one triconnecte… view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper shows dynamic planar graph isomorphism can be maintained in DynFO via FO formulas and polynomial auxiliary data.

read the letter

The headline result is that isomorphism between two planar graphs can be maintained under edge insertions and deletions using first-order logic formulas plus auxiliary relations of polynomial size. This puts the problem in DynFO and yields a constant-time parallel maintenance procedure with the same bounds. The abstract and the full construction make this placement explicit rather than leaving it as an open question in the DynFO program. Prior results covered other dynamic graph properties, but this one targets isomorphism on the planar case with a concrete maintenance scheme. The paper supplies the auxiliary schema, the update formulas, and an inductive argument that the relations stay correct after each update while preserving the necessary planarity invariants. That construction is the main technical contribution and it appears to avoid non-FO operations or size blow-ups. The argument covers both insertions and deletions for arbitrary sequences, which is the right level of generality for the claim. One soft spot is that the auxiliary data, while polynomial, likely carries large constants that would matter for any practical implementation; the paper does not claim otherwise. Another is that the formulas themselves are intricate, so a referee would want to verify that every case of planarity and isomorphism testing is handled without hidden assumptions. No circularity or fitting to parameters shows up in the argument. The work is aimed at people who study dynamic descriptive complexity and parallel algorithms for graphs with structure. Readers already following the DynFO line of results will find the techniques and the specific placement useful. It is a solid, self-contained membership proof that deserves a serious referee rather than a desk rejection. I would send it out for review.

Referee Report

0 major / 3 minor

Summary. The paper proves that dynamic planar graph isomorphism is in DynFO: given two planar graphs undergoing edge insertions and deletions, one can maintain (via first-order formulas and polynomial-size auxiliary relations) whether the graphs are isomorphic after each update. The result yields a dynamic constant-time parallel algorithm with polynomial auxiliary data. The proof proceeds by constructing an explicit FO-maintainable canonical representation (or embedding) that preserves planarity invariants under both insertions and deletions.

Significance. If the construction holds, the result is significant: it places a natural, non-trivial dynamic problem (planar isomorphism) into the restricted class DynFO, which is known to be contained in NC^1 and to admit constant-time parallel maintenance. The explicit FO formulas and inductive argument over update sequences constitute a concrete, falsifiable membership proof rather than an existence argument.

minor comments (3)

The abstract and introduction state the main theorem but do not include a high-level overview of the auxiliary schema or the key invariants maintained; adding a one-paragraph roadmap after the statement of Theorem 1 would improve readability.
Notation for the auxiliary relations (e.g., the canonical embedding predicates) is introduced in §3 but used without reminder in later inductive arguments; a short table summarizing the schema would help.
The paper assumes the input graphs remain planar after each update; while this is standard for the problem, a brief remark on how non-planar updates are rejected (or ignored) would clarify the model.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our result on maintaining planar graph isomorphism in DynFO and for recommending minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

Direct constructive proof with no circular reduction

full rationale

The paper establishes membership of dynamic planar graph isomorphism in DynFO by exhibiting an explicit collection of first-order formulas together with a polynomial-size auxiliary schema. These formulas are defined directly in terms of the input graph structure and the maintained auxiliary relations; correctness is shown by a standard inductive argument that each update (insertion or deletion) preserves planarity invariants and the isomorphism decision. No equation or auxiliary relation is defined in terms of the final isomorphism predicate itself, no parameter is fitted to a subset of instances and then re-used as a prediction, and no load-bearing step reduces to a self-citation whose own justification is internal to the present work. The derivation is therefore self-contained against the external definition of DynFO.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard axioms of first-order logic, the definition of DynFO, and basic properties of planar graphs and graph isomorphism; no free parameters or invented entities are introduced in the abstract.

axioms (2)

domain assumption First-order logic can express the required maintenance relations for planar graph isomorphism under updates
Invoked by the claim that FO formulas suffice; this is the central non-standard assumption for the result.
domain assumption Planar graphs remain planar under the considered edge insertions and deletions
Implicit in restricting the problem to planar graphs.

pith-pipeline@v0.9.0 · 5363 in / 1303 out tokens · 27167 ms · 2026-05-08T09:42:12.479306+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

34 extracted references · 33 canonical work pages

[1]

Graph isomorphism in quasipolynomial time [extended abstract]

L\' a szl\' o Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing , STOC '16, page 684–697, New York, NY, USA, 2016. Association for Computing Machinery. https://doi.org/10.1145/2897518.2897542 doi:10.1145/2897518.2897542

work page doi:10.1145/2897518.2897542 2016
[2]

Mix Barrington, Neil Immerman, and Howard Straubing

David A. Mix Barrington, Neil Immerman, and Howard Straubing. On uniformity within NC \( ^1 \) . J. Comput. Syst. Sci. , 41(3):274--306, 1990. https://doi.org/10.1016/0022-0000(90)90022-D doi:10.1016/0022-0000(90)90022-D

work page doi:10.1016/0022-0000(90)90022-d 1990
[3]

Battista and R

G. Battista and R. Tamassia. On-line maintenance of triconnected components with spqr-trees. Algorithmica , 15(4):302–318, April 1996. https://doi.org/10.1007/BF01961541 doi:10.1007/BF01961541

work page doi:10.1007/bf01961541 1996
[4]

Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees

Hans L Bodlaender. Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. Journal of Algorithms , 11(4):631--643, 1990. https://doi.org/https://doi.org/10.1016/0196-6774(90)90013-5 doi:https://doi.org/10.1016/0196-6774(90)90013-5

work page doi:10.1016/0196-6774(90)90013-5 1990
[5]

Stephen A. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control , 64(1-3):2--21, 1985. https://doi.org/10.1016/S0019-9958(85)80041-3 doi:10.1016/S0019-9958(85)80041-3

work page doi:10.1016/s0019-9958(85)80041-3 1985
[6]

Restricted space algorithms for isomorphism on bounded treewidth graphs

Bireswar Das, Jacobo Torán, and Fabian Wagner. Restricted space algorithms for isomorphism on bounded treewidth graphs. Information and Computation , 217:71--83, 2012. https://doi.org/https://doi.org/10.1016/j.ic.2012.05.003 doi:https://doi.org/10.1016/j.ic.2012.05.003

work page doi:10.1016/j.ic.2012.05.003 2012
[7]

Dynamic planar embedding is in DynFO

Samir Datta, Asif Khan, and Anish Mukherjee. Dynamic planar embedding is in DynFO . In J\' e r\^ o me Leroux, Sylvain Lombardy, and David Peleg, editors, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) , volume 272 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 39:1--39:15, Dagstuhl, Germany, ...

work page doi:10.4230/lipics.mfcs.2023.39 2023
[8]

Query maintenance under batch changes with small-depth circuits

Samir Datta, Asif Khan, Anish Mukherjee, Felix Tschirbs, Nils Vortmeier, and Thomas Zeume. Query maintenance under batch changes with small-depth circuits. In Rastislav Kr \' a lovic and Anton \' n Kucera, editors, 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, August 26-30, 2024, Bratislava, Slovakia , volume 306...

work page doi:10.4230/lipics.mfcs.2024.46 2024
[9]

Reachability Is in DynFO

Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. Reachability is in DynFO . J. ACM , 65(5):33:1--33:24, 2018. https://doi.org/10.1145/3212685 doi:10.1145/3212685

work page doi:10.1145/3212685 2018
[10]

Planar graph isomorphism is in log-space

Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar graph isomorphism is in log-space. ACM Trans. Comput. Theory , 14(2), sep 2022. https://doi.org/10.1145/3543686 doi:10.1145/3543686

work page doi:10.1145/3543686 2022
[11]

A Strategy for Dynamic Programs : Start over and Muddle through

Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. A strategy for dynamic programs: Start over and muddle through. Log. Methods Comput. Sci. , 15(2), 2019. https://doi.org/10.23638/LMCS-15(2:12)2019 doi:10.23638/LMCS-15(2:12)2019

work page doi:10.23638/lmcs-15(2:12)2019 2019
[12]

Graph Theory, 4th Edition , volume 173 of Graduate texts in mathematics

Reinhard Diestel. Graph Theory, 4th Edition , volume 173 of Graduate texts in mathematics . Springer, 2012

2012
[13]

Embedding and canonizing graphs of bounded genus in logspace

Michael Elberfeld and Ken-ichi Kawarabayashi. Embedding and canonizing graphs of bounded genus in logspace. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing , STOC '14, page 383–392, New York, NY, USA, 2014. Association for Computing Machinery. https://doi.org/10.1145/2591796.2591865 doi:10.1145/2591796.2591865

work page doi:10.1145/2591796.2591865 2014
[14]

Canonizing graphs of bounded tree width in logspace

Michael Elberfeld and Pascal Schweitzer. Canonizing graphs of bounded tree width in logspace. ACM Trans. Comput. Theory , 9(3):12:1--12:29, 2017. https://doi.org/10.1145/3132720 doi:10.1145/3132720

work page doi:10.1145/3132720 2017
[15]

Dynamic tree isomorphism via first-order updates

Kousha Etessami. Dynamic tree isomorphism via first-order updates. In Alberto O. Mendelzon and Jan Paredaens, editors, Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington, USA , pages 235--243. ACM Press, 1998. https://doi.org/10.1145/275487.275514 doi:10.1145/275487.275514

work page doi:10.1145/275487.275514 1998
[16]

Self-testing of quantum circuits , Year =

Martin Grohe and Oleg Verbitsky. Testing graph isomorphism in parallel by playing a game. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I , volume 4051 of Lecture Notes in Computer Science , ...

work page doi:10.1007/11786986 2006
[17]

A linear time implementation of spqr-trees

Carsten Gutwenger and Petra Mutzel. A linear time implementation of spqr-trees. In Joe Marks, editor, Graph Drawing, 8th International Symposium, GD 2000, Colonial Williamsburg, VA, USA, September 20-23, 2000, Proceedings , Lecture Notes in Computer Science, pages 77--90. Springer, 2000. https://doi.org/10.1007/3-540-44541-2\_8 doi:10.1007/3-540-44541-2\_8

work page doi:10.1007/3-540-44541-2 2000
[18]

H. V. Henderson and S. R. Searle. On deriving the inverse of a sum of matrices. SIAM Review , 23(1):53--60, 1981. https://doi.org/10.1137/1023004 doi:10.1137/1023004

work page doi:10.1137/1023004 1981
[19]

Italiano, Adam Karczmarz, Jakub Lacki, and Eva Rotenberg

Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, and Eva Rotenberg. Decremental spqr-trees for planar graphs. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms (ESA 2018) , volume 112 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 46:1--46:16, Dagstuhl, Germany, 2018....

work page doi:10.4230/lipics.esa.2018.46 2018
[20]

Italiano, Adam Karczmarz, Jakub Lacki, and Eva Rotenberg

Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, and Eva Rotenberg. Decremental spqr-trees for planar graphs. CoRR , abs/1806.10772, 2018. https://arxiv.org/abs/1806.10772 arXiv:1806.10772

work page arXiv 2018
[21]

J. E. Hopcroft and J. K. Wong. Linear time algorithm for isomorphism of planar graphs (preliminary report). In Proceedings of the Sixth Annual ACM Symposium on Theory of Computing , STOC '74, page 172–184, New York, NY, USA, 1974. Association for Computing Machinery. https://doi.org/10.1145/800119.803896 doi:10.1145/800119.803896

work page doi:10.1145/800119.803896 1974
[22]

Hopcroft and Robert Endre Tarjan

John E. Hopcroft and Robert Endre Tarjan. Dividing a graph into triconnected components. SIAM J. Comput. , 2(3):135--158, 1973. https://doi.org/10.1137/0202012 doi:10.1137/0202012

work page doi:10.1137/0202012 1973
[23]

The W eisfeiler- L eman dimension of planar graphs is at most 3

Sandra Kiefer, Ilia Ponomarenko, and Pascal Schweitzer. The W eisfeiler- L eman dimension of planar graphs is at most 3. J. ACM , 66(6):44:1--44:31, 2019. https://doi.org/10.1145/3333003 doi:10.1145/3333003

work page doi:10.1145/3333003 2019
[24]

A logspace algorithm for tree canonization (extended abstract)

Steven Lindell. A logspace algorithm for tree canonization (extended abstract). In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada , pages 400--404, 1992. https://doi.org/10.1145/129712.129750 doi:10.1145/129712.129750

work page doi:10.1145/129712.129750 1992
[25]

Jenish C. Mehta. Dynamic complexity of planar 3-connected graph isomorphism. In Edward A. Hirsch, Sergei O. Kuznetsov, Jean - \' E ric Pin, and Nikolay K. Vereshchagin, editors, Computer Science - Theory and Applications - 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014. Proceedings , Lecture Notes in Comp...

work page doi:10.1007/978-3-319-06686-8 2014
[26]

Dyn- FO : A parallel, dynamic complexity class

Sushant Patnaik and Neil Immerman. Dyn- FO : A parallel, dynamic complexity class. In Victor Vianu, editor, Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota, USA , pages 210--221. ACM Press, 1994. https://doi.org/10.1145/182591.182614 doi:10.1145/182591.182614

work page doi:10.1145/182591.182614 1994
[27]

Dyn- FO : A parallel, dynamic complexity class

Sushant Patnaik and Neil Immerman. Dyn- FO : A parallel, dynamic complexity class. J. Comput. Syst. Sci. , 55(2):199--209, 1997. https://doi.org/10.1006/JCSS.1997.1520 doi:10.1006/JCSS.1997.1520

work page doi:10.1006/jcss.1997.1520 1997
[28]

P. N. Shivakumar and Kim Ho Chew. A sufficient condition for nonvanishing of determinants. Proc. Amer. Math. Soc. , 43:63--66, 1974. https://doi.org/10.2307/2039326 doi:10.2307/2039326

work page doi:10.2307/2039326 1974
[29]

The isomorphism problem for planar 3-connected graphs is in unambiguous logspace

Thomas Thierauf and Fabian Wagner. The isomorphism problem for planar 3-connected graphs is in unambiguous logspace. Theory Comput. Syst. , 47(3):655--673, 2010. https://doi.org/10.1007/S00224-009-9188-4 doi:10.1007/S00224-009-9188-4

work page doi:10.1007/s00224-009-9188-4 2010
[30]

On the hardness of graph isomorphism

Jacobo Tor\' a n. On the hardness of graph isomorphism. SIAM Journal on Computing , 33(5):1093--1108, 2004. https://doi.org/10.1137/S009753970241096X doi:10.1137/S009753970241096X

work page doi:10.1137/s009753970241096x 2004
[31]

W. T. Tutte. How to draw a graph. Proceedings of the London Mathematical Society , s3-13(1):743--767, 1963. https://doi.org/https://doi.org/10.1112/plms/s3-13.1.743 doi:https://doi.org/10.1112/plms/s3-13.1.743

work page doi:10.1112/plms/s3-13.1.743 1963
[32]

Dynamic complexity of parity exists queries

Nils Vortmeier and Thomas Zeume. Dynamic complexity of parity exists queries. Log. Methods Comput. Sci. , 17(4), 2021. https://doi.org/10.46298/LMCS-17(4:9)2021 doi:10.46298/LMCS-17(4:9)2021

work page doi:10.46298/lmcs-17(4:9)2021 2021
[33]

Weinberg

L. Weinberg. A simple and efficient algorithm for determining isomorphism of planar triply connected graphs. IEEE Transactions on Circuit Theory , 13(2):142--148, 1966. https://doi.org/10.1109/TCT.1966.1082573 doi:10.1109/TCT.1966.1082573

work page doi:10.1109/tct.1966.1082573 1966
[34]

2-isomorphic graphs

Hassler Whitney. 2-isomorphic graphs. American Journal of Mathematics , 55(1):245--254, 1933. URL: http://www.jstor.org/stable/2371127

work page arXiv 1933