Planarity testing revisited

DOI10.1007/978-3-642-20877-5_52zbMATH Open1331.68102OpenAlexW1502365342MaRDI QIDQ3010433FDOQ3010433

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

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

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)

Cites Work

• Title not available (Why is that?)
• Computational Complexity
• Undirected connectivity in log-space
• Efficient Planarity Testing
• Nondeterministic Space is Closed under Complementation
• The method of forced enumeration for nondeterministic automata
• 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
• 3-connected Planar Graph Isomorphism is in Log-space
• The complexity of planarity testing
• Parallel Algorithms in Graph Theory: Planarity Testing
• Symmetric Complementation
• Space efficient algorithms for some graph theoretical problems
• Title not available (Why is that?)
• Planarity testing in parallel
• Planarity testing revisited
• Title not available (Why is that?)

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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Testing contractibility in planar rips complexes
• Title not available (Why is that?)
• 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)