Space complexity: what makes planar graphs special?

zbMATH Open1394.68174MaRDI QIDQ4584898FDOQ4584898

Authors: Samir Datta, Raghav Kulkarni 

Publication date: 4 September 2018

Full work available at URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/26/22

Recommendations

• Publication:5753968
• Space complexity of optimization problems in planar graphs
• The Maximum Independent Set Problem in Planar Graphs
• scientific article; zbMATH DE number 1500509
• \(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability

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)

Cited In (3)

• The complexity of the Hajós calculus for planar graphs
• Space complexity of optimization problems in planar graphs
• Computing planarity in computable planar graphs

This page was built for publication: Space complexity: what makes planar graphs special?

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