Space complexity: what makes planar graphs special?

MaRDI QIDQ4584898zbMATH OpenFDO

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

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4189751
• 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

Cited in

(3)

• The complexity of the Hajós calculus for planar graphs
• Computing planarity in computable planar graphs
• Space complexity of optimization problems in 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)