Planarity testing revisited

DOI10.1007/978-3-642-20877-5_52MaRDI QIDQ3010433zbMATH OpenOpenAlexFDO

Authors Samir Datta, Gautam Prakriya

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• The complexity of planarity testing
• scientific article; zbMATH DE number 1500509
• Graph Drawing
• A new planarity test
• A linear algorithm for embedding planar graphs using PQ-trees

Cites work

• scientific article; zbMATH DE number 3133252 (Why is no real title available?)
• scientific article; zbMATH DE number 1332655 (Why is no real title available?)
• scientific article; zbMATH DE number 1500509 (Why is no real title available?)
• 3-connected Planar Graph Isomorphism is in Log-space
• Computational Complexity
• Deterministically isolating a perfect matching in bipartite planar graphs
• Directed planar reachability is in unambiguous log-space
• Efficient Planarity Testing
• Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
• Nondeterministic Space is Closed under Complementation
• Parallel Algorithms in Graph Theory: Planarity Testing
• Planarity testing in parallel
• Planarity testing revisited
• Space efficient algorithms for some graph theoretical problems
• Symmetric Complementation
• The complexity of planarity testing
• The method of forced enumeration for nondeterministic automata
• Undirected connectivity in log-space

Cited in

(12)

• Upward Planarity Testing: A Computational Study
• Embedding and canonizing graphs of bounded genus in logspace
• Fast incremental planarity testing
• Classification and detection of obstructions to planarity
• scientific article; zbMATH DE number 6863594 (Why is no real title available?)
• scientific article; zbMATH DE number 6863595 (Why is no real title available?)
• scientific article; zbMATH DE number 7561324 (Why is no real title available?)
• Testing contractibility in planar rips complexes
• scientific article; zbMATH DE number 1500509 (Why is no real title available?)
• The complexity of planarity testing
• A Planarity Test via Construction Sequences
• Planarity testing revisited

This page was built for publication: Planarity testing revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3010433)