2026-07-23T15:48:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2314 2024-03-06T10:33:16Z ddc:004 open_access

Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space Datta, Samir Nimbhorkar, Prajakta Thierauf, Thomas Wagner, Fabian Graph isomorphism K_{3,3}-free graphs K_5-free graphs log-space Graph isomorphism is an important and widely studied computational problem with a yet unsettled complexity. However, the exact complexity is known for isomorphism of various classes of graphs. Recently, \cite{DLNTW09} proved that planar isomorphism is complete for log-space. We extend this result %of \cite{DLNTW09} further to the classes of graphs which exclude $K_{3,3}$ or $K_5$ as a minor, and give a log-space algorithm. Our algorithm decomposes $K_{3,3}$ minor-free graphs into biconnected and those further into triconnected components, which are known to be either planar or $K_5$ components \cite{Vaz89}. This gives a triconnected component tree similar to that for planar graphs. An extension of the log-space algorithm of \cite{DLNTW09} can then be used to decide the isomorphism problem. For $K_5$ minor-free graphs, we consider $3$-connected components. These are either planar or isomorphic to the four-rung mobius ladder on $8$ vertices or, with a further decomposition, one obtains planar $4$-connected components \cite{Khu88}. We give an algorithm to get a unique decomposition of $K_5$ minor-free graphs into bi-, tri- and $4$-connected components, and construct trees, accordingly. Since the algorithm of \cite{DLNTW09} does not deal with four-connected component trees, it needs to be modified in a quite non-trivial way. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Samir Datta and Prajakta Nimbhorkar and Thomas Thierauf and Fabian Wagner 2009 Is Part Of LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2009.2314 urn:nbn:de:0030-drops-23144 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2314 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode