The complexity of planarity testing
type: Item
instance of: scholarly article
title: The complexity of planarity testing
zbMATH Open document ID: 1072.68045
author: Eric Allender
author: Meena Mahajan
published in: Information and Computation
publication date: 2004-11-23T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 2118415
zbMATH Keywords: Planar graphs
zbMATH Keywords: Symmetric logspace
MaRDI profile type: Publication
full work available at URL: j.ic.2003.09.002
OpenAlex ID: W2028753111
cites work: Q4501524
cites work: An O (log( n ) 4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: Problems complete for deterministic logarithmic space
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Constant Depth Reducibility
cites work: Computing an st-numbering
cites work: Counting quantifiers, successor relations, and logarithmic space
cites work: Q3883524
cites work: Q3684121
cites work: Boolean complexity classes vs. their arithmetic analogs
cites work: Efficient Planarity Testing
cites work: Nondeterministic Space is Closed under Complementation
cites work: Q2762791
cites work: Parallel Algorithms in Graph Theory: Planarity Testing
cites work: Space efficient algorithms for some graph theoretical problems
cites work: Turing machines that take advice
cites work: Q5596083
cites work: Parallel ear decomposition search (EDS) and st-numbering in graphs
cites work: Q4938661
cites work: Q4230323
cites work: Q4234059
cites work: Making Nondeterminism Unambiguous
cites work: Symmetric Complementation
cites work: Planarity testing in parallel
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: The method of forced enumeration for nondeterministic automata
cites work: Toward a theory of crossing numbers
cites work: Q5607111
cites work: Q4156452
cites work: The complexity of graph connectivity
cites work: Relativized circuit complexity
DOI: 10.1016/J.IC.2003.09.002
description: scientific article; zbMATH DE number 2118415