期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 [DLN+09] proved that planar graph isomorphism is complete for log-space.
We extend this result of [DLN+09] further
to the classes of graphs which exclude K33 or K5 as
a minor, and give a log-space algorithm.
Our algorithm for K33 minor-free graphs proceeds by decomposition into triconnected
components, which are known to be either planar or K5 components [Vaz89]. This gives a triconnected
component tree similar to that for planar graphs. An extension of the log-space algorithm of [DLN+09]
can then be used to decide the isomorphism problem.
For K5 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 [Khu88].
We give an algorithm to get a unique
decomposition of K5 minor-free graphs into bi-, tri- and 4-connected components,
and construct trees, accordingly.
Since the algorithm of [DLN+09] does
not deal with four-connected component trees, it needs to be modified in a quite non-trivial way.
