The complexity of planarity testing

DOI10.1016/j.ic.2003.09.002zbMath1072.68045OpenAlexW2028753111MaRDI QIDQ1887150

Meena Mahajan, Eric W. Allender

Publication date: 23 November 2004

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2003.09.002

zbMATH Keywords

Planar graphsSymmetric logspace

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (11)

Equivalence classes and conditional hardness in massively parallel computations ⋮ The Isomorphism Problem for k-Trees Is Complete for Logspace ⋮ Depth-first search in directed planar graphs, revisited ⋮ Constant work-space algorithms for facility location problems ⋮ Sublinear-space approximation algorithms for Max \(r\)-SAT ⋮ Planarity Testing Revisited ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ Unnamed Item ⋮ Approximation in (Poly-) logarithmic space ⋮ Planar and grid graph reachability problems ⋮ Approximation in (Poly-) Logarithmic Space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Turing machines that take advice
• Relativized circuit complexity
• Parallel ear decomposition search (EDS) and st-numbering in graphs
• The method of forced enumeration for nondeterministic automata
• Space efficient algorithms for some graph theoretical problems
• Computing an st-numbering
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Planarity testing in parallel
• Counting quantifiers, successor relations, and logarithmic space
• Relationships between nondeterministic and deterministic tape complexities
• Constant Depth Reducibility
• A taxonomy of problems with fast parallel algorithms
• Symmetric Complementation
• Problems complete for deterministic logarithmic space
• Nondeterministic Space is Closed under Complementation
• Parallel Algorithms in Graph Theory: Planarity Testing
• Efficient Planarity Testing
• Boolean complexity classes vs. their arithmetic analogs
• Making Nondeterminism Unambiguous
• The complexity of graph connectivity
• An O (log( n ) ^4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
• Toward a theory of crossing numbers

This page was built for publication: The complexity of planarity testing