Planar Graph Isomorphism Is in Log-Space

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

doi:10.1145/3543686

Planar Graph Isomorphism Is in Log-Space

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

Algorithms

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

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. The gap between the known upper and lower bounds continues to be very significant for many subclasses of graphs as well.
We bridge the gap for a natural and important class of graphs, namely, planar graphs, by presenting a log-space upper bound that matches the known log-space hardness. In fact, we show a stronger result that planar graph canonization is in log-space.

Original language	English
Journal	ACM Transactions on Computation Theory
Volume	14
Issue number	2
Pages (from-to)	1-33
Number of pages	33
ISSN	1942-3454
DOIs	https://doi.org/10.1145/3543686
Publication status	Published - 2022

Keywords

Computational complexity
log-space
planar graph isomorphism

Access to Document

10.1145/3543686

3543686Final published version, 569 KBLicence: CC BY

https://dl.acm.org/doi/pdf/10.1145/3543686

Cite this

@article{f73e611b6bcc40e58ede12f8e2b754e1,

title = "Planar Graph Isomorphism Is in Log-Space",

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. The gap between the known upper and lower bounds continues to be very significant for many subclasses of graphs as well.We bridge the gap for a natural and important class of graphs, namely, planar graphs, by presenting a log-space upper bound that matches the known log-space hardness. In fact, we show a stronger result that planar graph canonization is in log-space.",

keywords = "Computational complexity, log-space, planar graph isomorphism, Computational complexity, log-space, planar graph isomorphism",

author = "Samir Datta and Nutan Limaye and Prajakta Nimbhorkar and Thomas Thierauf and Fabian Wagner",

year = "2022",

doi = "10.1145/3543686",

language = "English",

volume = "14",

pages = "1--33",

journal = "ACM Transactions on Computation Theory",

issn = "1942-3454",

publisher = "Association for Computing Machinery",

number = "2",

}

TY - JOUR

T1 - Planar Graph Isomorphism Is in Log-Space

AU - Datta, Samir

AU - Limaye, Nutan

AU - Nimbhorkar, Prajakta

AU - Thierauf, Thomas

AU - Wagner, Fabian

PY - 2022

Y1 - 2022

N2 - 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. The gap between the known upper and lower bounds continues to be very significant for many subclasses of graphs as well.We bridge the gap for a natural and important class of graphs, namely, planar graphs, by presenting a log-space upper bound that matches the known log-space hardness. In fact, we show a stronger result that planar graph canonization is in log-space.

AB - 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. The gap between the known upper and lower bounds continues to be very significant for many subclasses of graphs as well.We bridge the gap for a natural and important class of graphs, namely, planar graphs, by presenting a log-space upper bound that matches the known log-space hardness. In fact, we show a stronger result that planar graph canonization is in log-space.

KW - Computational complexity

KW - log-space

KW - planar graph isomorphism

KW - Computational complexity

KW - log-space

KW - planar graph isomorphism

U2 - 10.1145/3543686

DO - 10.1145/3543686

M3 - Journal article

SN - 1942-3454

VL - 14

SP - 1

EP - 33

JO - ACM Transactions on Computation Theory

JF - ACM Transactions on Computation Theory

IS - 2

ER -

Planar Graph Isomorphism Is in Log-Space

Abstract

Keywords

Access to Document

Fingerprint

Cite this