License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09421.6
URN: urn:nbn:de:0030-drops-24169
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2416/
Go to the corresponding Portal

Datta, Samir ; Limaye, Nutan ; Nimbhorkar, Prajakta ; Thierauf, Thomas ; Wagner, Fabian

Planar Graph Isomorphism is in Log-Space

pdf-format:
09421.WagnerFabian.Paper.2416.pdf (0.4 MB)

Abstract

Graph Isomorphism is the prime example of a computational problem with a wide
difference between the best known lower and upper bounds on its complexity. There
is a significant gap between extant lower and upper bounds for planar graphs as well.
We bridge the gap for this natural and important special case by presenting an upper
bound that matches the known log-space hardness [JKMT03]. In fact, we show the
formally stronger result that planar graph canonization is in log-space. This improves the
previously known upper bound of AC1 [MR91].
Our algorithm first constructs the biconnected component tree of a connected planar
graph and then refines each biconnected component into a triconnected component
tree. The next step is to log-space reduce the biconnected planar graph isomorphism and
canonization problems to those for 3-connected planar graphs, which are known to be in
log-space by [DLN08]. This is achieved by using the above decomposition, and by making
significant modifications to Lindell’s algorithm for tree canonization, along with changes
in the space complexity analysis.
The reduction from the connected case to the biconnected case requires further new
ideas including a non-trivial case analysis and a group theoretic lemma to bound the
number of automorphisms of a colored 3-connected planar graph.

BibTeX - Entry

@InProceedings{datta_et_al:DagSemProc.09421.6,
  author =	{Datta, Samir and Limaye, Nutan and Nimbhorkar, Prajakta and Thierauf, Thomas and Wagner, Fabian},
  title =	{{Planar Graph Isomorphism is in Log-Space}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--32},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9421},
  editor =	{Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2010/2416},
  URN =		{urn:nbn:de:0030-drops-24169},
  doi =		{10.4230/DagSemProc.09421.6},
  annote =	{Keywords: Planar Graphs, Graph Isomorphism, Logspace}
}

Keywords: Planar Graphs, Graph Isomorphism, Logspace
Collection: 09421 - Algebraic Methods in Computational Complexity
Issue Date: 2010
Date of publication: 19.01.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI