scientific article; zbMATH DE number 1500509

MaRDI QIDQ4501524zbMATH OpenFDO

Authors Meena Mahajan, Eric Allender

Publication date 26 April 2001

zbMATH Keywords

computational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The complexity of planarity testing
• Planarity testing revisited
• On the computational complexity of upward and rectilinear planarity testing
• scientific article; zbMATH DE number 6863595
• On the complexity of HV-rectilinear planarity testing
• The Complexity of Planar Counting Problems
• Computing planarity in computable planar graphs
• On the linearity of testing planarity of graphs
• Hierarchical planarity testing algorithms
• scientific article; zbMATH DE number 3960992

Cited in

(16)

• Testing approximate symmetry in the plane is NP-hard
• The combinatorial approach yields an NC algorithm for computing Pfaffians
• The complexity of planarity testing
• The complexity of oblivious plans for orienting and distinguishing polygonal parts
• The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
• On the computational complexity of upward and rectilinear planarity testing
• Testing Full Outer-2-planarity in Linear Time
• A Planarity Test via Construction Sequences
• Planarity testing revisited
• Classification and detection of obstructions to planarity
• Testing contractibility in planar rips complexes
• scientific article; zbMATH DE number 17809 (Why is no real title available?)
• Space complexity: what makes planar graphs special?
• scientific article; zbMATH DE number 6863595 (Why is no real title available?)
• Fully-dynamic planarity testing in polylogarithmic time
• Practical Experience with Hanani-Tutte for Testing c-Planarity

This page was built for publication:

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