Planarity Testing Revisited
From MaRDI portal
Publication:3010433
DOI10.1007/978-3-642-20877-5_52zbMath1331.68102OpenAlexW1502365342MaRDI QIDQ3010433
Publication date: 1 July 2011
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-20877-5_52
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Cites Work
- The method of forced enumeration for nondeterministic automata
- Space efficient algorithms for some graph theoretical problems
- Planarity testing in parallel
- The complexity of planarity testing
- Deterministically isolating a perfect matching in bipartite planar graphs
- Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.
- Directed Planar Reachability Is in Unambiguous Log-Space
- Planarity Testing Revisited
- 3-connected Planar Graph Isomorphism is in Log-space
- Undirected connectivity in log-space
- Symmetric Complementation
- Nondeterministic Space is Closed under Complementation
- Parallel Algorithms in Graph Theory: Planarity Testing
- Efficient Planarity Testing
- Computational Complexity
- Unnamed Item
- Unnamed Item
- Unnamed Item