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

Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › 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.

Originalsprog	Engelsk
Tidsskrift	ACM Transactions on Computation Theory
Vol/bind	14
Udgave nummer	2
Sider (fra-til)	1-33
Antal sider	33
ISSN	1942-3454
DOI	https://doi.org/10.1145/3543686
Status	Udgivet - 2022

Emneord

Computational complexity
log-space
planar graph isomorphism

Adgang til dokumentet

10.1145/3543686

3543686Forlagets udgivne version, 569 KBLicens: CC BY

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

Citationsformater

@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

Emneord

Adgang til dokumentet

Fingeraftryk

Citationsformater